Design of Improved Approximation Algorithms for Combinatorial Optimization Problems

近似算法是求解组合优化问题的有效算法，它能保证得到的解与最优解相差一定的因子。由于各种原因，理论计算机科学的这一领域在过去的十年里有了巨大的发展。首先，设计这种近似算法的几个重要技术已经被发现，包括凸优化技术和更具体的半定规划的使用。此外，复杂性理论的重大进展已经导致了强不可近似性的结果，有时甚至表明，对于某些问题，平凡的近似算法给出了人们所希望的最佳保证（除非P=NP）。在这个项目中，这是一个PI之前的职业生涯奖的延续，重点是设计用于推导近似算法的一般技术，以及获得几个经典的近似算法的改进。硬优化问题所要考虑的问题包括路由问题、旅行商问题、Steiner树问题、稀疏割问题和调度问题。

Approximation algorithms are efficient algorithms for combinatorialoptimization problems that deliver solutions which are guaranteed tobe within a certain factor of the optimum. This area of theoreticalcomputer science has seen a tremendous growth in the last decade forvarious reasons. First, several important techniques for designingsuch approximation algorithms have been discovered, including the useof convex optimization techniques and more specifically semidefiniteprogramming. Also, major advances in complexity theory have lead tostrong non-approximability results, sometimes even showing that forcertain problems trivial approximation algorithms give the bestguarantee one could hope for (unless P=NP).In this project, which is a continuation of the PI prior CAREER award,the emphasis is both on the design of general techniques for derivingapproximation algorithms and also on obtaining improved approximationalgorithms for several classical hard optimization problems. Theproblems to be considered include routing problems, the travelingsalesman problem, the Steiner tree problem, the sparsest cut problem,and scheduling problems.