Design of Improved Approximation Algorithms for Combinatorial Optimization Problems

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Approximation algorithms are efficient algorithms for combinatorial optimization problems that deliver solutions which are guaranteed to be within a certain factor of the optimum. This area of theoretical computer science has seen a tremendous growth in the last decade for various reasons. First, several important techniques for designing such approximation algorithms have been discovered, including the use of convex optimization techniques and more specifically semidefinite programming. Also, major advances in complexity theory have lead to strong non-approximability results, sometimes even showing that for certain problems trivial approximation algorithms give the best guarantee 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 deriving approximation algorithms and also on obtaining improved approximation algorithms for several classical hard optimization problems. The problems to be considered include routing problems, the traveling salesman problem, the Steiner tree problem, the sparsest cut problem, and scheduling problems.