今年六月于捷克布拉格举行的计算理论研讨会（STOC）上，上海纽约大学计算机科学助理教授薛杰的三篇论文成功入选。
自1969年创办以来，STOC一直是理论计算机科学领域最具声望的国际会议之一，大会议题涵盖算法、计算复杂性理论及相关领域的前沿进展。
“STOC是备受学术界认可的一大会议，薛教授在同一年有三篇论文入选，充分体现了他的科研实力，我们对此深感自豪。这也展现了上纽大在追求科研卓越方面的不懈努力。” 上海纽约大学计算机科学、数据科学与工程学部主任Nasir Memon表示。
薛杰教授的研究聚焦于几何问题与图论中的高效算法设计，不仅提出了更快速的算法方案，同时也推动了相关领域的理论发展。
研究一：最小距离下的高效匹配
该论文探讨了几何多重匹配问题（Geometric Multimatching Problem）— 如何在欧几里得空间中为两组点进行匹配，并使连接路径的总距离尽可能短。
薛教授解释道：“可以把它想象成地图上的住户与商店。每个住户需要连接到至少一家商店，同时每家商店需要连接到至少一家住户，而我们的目标就是在满足需求的同时，让整体出行距离最小化。”
论文提出了两种高效的近似算法来解决这一问题。这些算法不仅适用于欧几里得空间，也能推广至更一般的度量空间中。
阅读原文 – Approximation Algorithms for the Geometric Multimatching Problem
研究二：稀疏图中复杂模式的快速检测
该论文致力于解决如何在大规模稀疏图中高效查找或计数某种特定模式的问题。论文中所考虑的模式为图中的一些满足彼此之间距离约束的结点。想象在一个巨大的网络中（比如社交关系图谱或城市交通网络），你想要快速找到满足某些条件的结点组合，例如：组内结点之间的距离必须都至少为3，同时又至多为10。这类问题在数据处理中较为常见。
“在论文中，我们提出了一系列高效算法，用以在稀疏图中查找或计数此种模式。这些算法显著提升了现有方法的运行效率。” 薛教授解释说，“在设计算法时，我们还发展出了一套解决此类问题的通用理论工具。这些工具有望应用于其他相关问题。”
阅读原文 – Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs
研究三：图中“问题子结构”的消除
该论文研究的是算法图论中的一类基础性问题：如何在一个给定的图中删除尽可能少的节点，以消除所有不希望出现的子图。这一类问题被称为“子图命中”（Subgraph Hitting），是图优化研究中许多重要问题的一个推广。
论文证明了：只要输入的图中存在小规模的“分隔集”（即一种删除后可将图分为若干规模相当的子图的结构），子图命中问题便能在亚指数时间内得以解决。这一结果不仅显著拓展了以往的研究工作，也深化了学界对相关问题的理解。
阅读原文 – Subexponential Parameterized Algorithms for Hitting Subgraphs