CAREER: Metric Geometry Techniques for Approximation Algorithms

组合优化问题在许多领域有着重要的应用。它们出现在运筹学、机器学习、VLSI设计、计算生物学等许多领域。然而，许多优化问题是NP难的，因此除非P=NP，否则不能在多项式时间内精确地求解。因此，寻找近似算法是很自然的，也就是只找到近似解的高效算法。近似算法的设计和分析是一个非常活跃的研究领域。在过去的三十年里，出现了各种解决组合优化问题的方法。然而，尽管取得了重大进展，但许多重要问题仍然悬而未决。本研究项目旨在促进度量几何技术在解决组合优化问题中的应用，探索设计近似算法的新方法，并开发工具来分析现实生活中的近似算法的性能。这一研究项目将具有重要的理论意义和实际意义，并将促进许多科学和工程领域中重要应用问题的近似算法的发展。具体地说，PI将致力于以下问题。*传统上，大多数研究集中在分析近似算法的最坏情况下的性能。然而，实践者观察到，在实践中出现的组合优化问题的实例通常不像最坏的情况的实例那么难。PI将研究各种组合优化问题的半随机模型，并开发在半随机实例上表现良好的近似算法。这也许可以解释我们在实践中看到的东西。*最近由科特发起的关于逼近难度的研究发现，独特的博弈问题是许多问题逼近算法发展的一个组合障碍。PI将研究解决独特游戏问题的算法技术。*PI将研究线性规划(LP)和半定规划(SDP)松弛的提升和投影层次，分析它们的完整性差距，并设计使用这些层次的次指数近似算法。*理论计算机科学的某些领域与纯数学之间存在密切联系。为了解决组合优化中的一些问题，我们需要在分析中解决紧密相连的开放问题。PI将探索几个与计算机科学和数学有很深联系的问题。

Combinatorial optimization problems are of great importance to numerous applications. They arise in operations research, machine learning, VLSI design, computational biology and many other areas. Many optimization problems however are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. It is natural therefore to look for approximation algorithms, efficient algorithms that find only approximate solutions. Design and analysis of approximation algorithms is a very active research area. Various approaches for solving combinatorial optimization problems have appeared in the last three decades. However, despite significant progress, many important problems are still open. This research project aims to advance the application of metric geometry techniques for solving combinatorial optimization problems, investigate new methods for designing approximation algorithms, and develop tools for analyzing the performance of approximation algorithms on real-life instances. This research project will be both theoretically important and practically relevant and it will lead to development of approximation algorithms for important applied problems that occur in many fields of science and engineering. Specifically, the PI will work on the following problems.* Traditionally most research has focused on analyzing the worst case performance of approximation algorithms. However, practitioners observe that instances of combinatorial optimization problems that arise in practice are often not as hard as worst case instances. The PI will study semi-random models for various combinatorial optimization problems, and develop approximation algorithms that perform well on semi-random instances. This can perhaps explain what we see in practice.* Recent research in the hardness of approximation initiated by Khot identified Unique Games Problem as a combinatorial obstacle to the development of approximation algorithms for many problems. The PI will study algorithmic techniques for solving the Unique Games Problem.* The PI will study lift-and-project hierarchies of linear programming (LP) and semi-definite programming (SDP) relaxations, analyze their integrality gaps, and design subexponential approximation algorithms that use these hierarchies.* There is a close connection between some areas of theoretical computer science and pure mathematics. To settle down some problems in combinatorial optimization, we need to resolve closely connected open problems in analysis. The PI will explore several problems with deep ties to computer science and mathematics.