Design of Improved Approximation Algorithms for Combinatorial Optimization Problems

点击翻译按钮获取中文摘要

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.