CAREER: Metric Geometry Techniques for Approximation Algorithms

组合优化问题在许多应用中具有重要意义。它们出现在运筹学、机器学习、超大规模集成电路设计、计算生物学和许多其他领域。然而，许多优化问题是NP困难的，因此不能在多项式时间内精确地解决，除非P=NP。因此寻找近似算法是很自然的，高效的算法只能找到近似解。设计和分析近似算法是一个非常活跃的研究领域。在过去的三十年中出现了各种解决组合优化问题的方法。然而，尽管取得了重大进展，许多重要问题仍未解决。本研究项目旨在推进度量几何技术在解决组合优化问题中的应用，研究设计近似算法的新方法，并开发用于分析近似算法在实际实例中的性能的工具。该研究项目将具有重要的理论意义和实际意义，并将导致在许多科学和工程领域出现的重要应用问题的近似算法的发展。具体来说，PI将处理以下问题。*传统上，大多数研究都集中在分析近似算法的最坏情况性能上。然而，从业者观察到，在实践中出现的组合优化问题的实例通常没有最坏情况的实例那么难。PI将研究各种组合优化问题的半随机模型，并开发在半随机实例上表现良好的近似算法。这也许可以解释我们在实践中看到的情况。*最近由Khot发起的关于近似硬度的研究将唯一博弈问题确定为许多问题近似算法发展的组合障碍。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.