New directions in Approximation Algorithms for NP-hard problems

Princeton University, Princeton NJ

Investigators

Abstract

Many optimization problems are NP-hard, and computing approximate solutions is an attractive way to cope with NP-hardness. The effort to understand the approximation properties of NP problems has occupied the center stage of theoretical computer science in the past decade. Despite many successes in this field, the status of some of the basic problems ---- metric tsp, vertex cover, graph coloring, sparsest cut etc.---is still open. The project consists of designing new approaches for computing approximate solutions to these problems. Any results for these central problems should generalize to many other problems. The tools used involve sophisticated geometric arguments, and "lift and project" technique from polyhedral combinatorics. Another goal is to develop a comprehensive framework for designing approximation algorithms without relying on semidefinite programming (SDP). Many recent approximation algorithms use SDP, which is not particularly efficient in practice. The goal in this project is to replace SDP with simpler algorithms based upon eigenvalue computations. Another aspect of the project is to prove lowerbounds to complement any new algorithms, or to rule out the existence of some of the above algorithms. The lowerbounds attempted would be both for all polynomial-time algorithms ---this would use PCPs---and for specific algorithms arising from lift and project methods. (The latter consists of viewing lift and project methods as a weak computational model.) Broader impact of this project include dissemination efforts such as new innovative courses in graduate and undergraduate education, new text book, and survey articles on current research.