AF: Small: Mathematical Programming Methods in Approximation

Princeton University, Princeton NJ

Investigators

Abstract

Mathematical programming techniques like linear programming and semidefinite programming have firmly established themselves as valuable tools in the approximation algorithm design toolkit. They are often used as tractable relaxations to hard combinatorial optimization problems and as design guides to obtain approximation algorithms. This project attempts to enhance our understanding of the strengths and weaknesses of mathematical programming techniques for several fundamental optimization problems and proposes to investigate general methods to strengthen our currently known mathematical programming techniques. The broad goals of this project are the following: (a) Attempt to devise better algorithms for unique games ? a constraint satisfaction problem that is known to capture the limitations of current semidefinite programming methods used in approximation algorithms. Beating the current best algorithms will necessarily involve developing new techniques that overcome the limitations of current SDP approaches. (b) Understand the structure of strengthened relaxations obtained by lift-and-project procedures and develop techniques to exploit the additional information provided by these stronger relaxations to obtain better approximation algorithms. (c) Work towards closing large gaps in our understanding of the approximability of fundamental optimization problems. Successfully achieving the project goals will entail significant advances in the state of the art for approximation algorithms. The research could potentially develop tools and techniques with broad applicability to several optimization problems. Course materials for graduate and undergraduate courses will be developed distilling research results of this project, as well as new developments in the field.