[talks] D Steurer preFPO
Melissa Lawson
mml at CS.Princeton.EDU
Wed Feb 24 09:17:36 EST 2010
David Steurer will present his preFPO on Monday March 1 at 3PM in Room 402. The
members of his committee are: Sanjeev Arora, advisor; Russell Impagliazzo (IAS), Boaz
Barak,
Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk. His
abstract
follows below.
-----------------------------------------------------------
On Strengths and Limits of Relaxations for Combinatorial Optimization
Mathematical programming relaxations are powerful tools for solving or
approximating combinatorial optimization problems. This thesis
explores the strengths and limits of these tools for a selection of
basic optimization problems.
A central open question in this context is the Unique Games Conjecture
(Khot 2002), which asserts that a certain optimization problem, called
Unique Games, is hard to approximate in a certain regime. In recent
years, a sequence of works established that this conjecture has
profound implications: If the conjecture is true, then a certain
semidefinite relaxations, called Basic-SDP, is optimal for a large
range of optimization problems, in the sense that no efficient
relaxation can achieve a better approximation for any of these
problems.
We make the following contributions towards a better understanding of
the Unique Games Conjecture and semidefinite relaxations of
combinatorial optimization problems:
- We exhibit an optimal rounding scheme for constraint satisfaction
problems (CSPs), a well-studied class of combinatorial optimization
problem. The guarantee of the scheme matches the integrality gap of
the Basic-SDP relaxation for every CSP. In contrast to many previous
rounding algorithms, our scheme is generic and very simple.
Moreover, it allows for a principled analysis.
- Using our rounding scheme and a framework (Arora and Kale 2007) for
solving semidefinite relaxations, we develop an approximation
algorithm for CSPs whose approximation guarantee matches the
integrality of the Basic-SDP relaxation and whose running time is
quasi-linear. Assuming the Unique Games Conjecture, no polynomial
time algorithm can have a better approximation guarantee.
- We confirm the Unique Games Conjecture for a restricted model of
computation given by a hierarchy of semidefinite relaxations. In
particular, we show that for every CSP, the integrality gap of the
Basic-SDP cannot be improved by adding a large class of valid
inequalities. It was a long-standing open question whether such
stronger relaxation could lead to better approximation algorithms
for problems like Max-Cut or Multiway-Cut. Our result answers this
question in the negative.
- Finally, we establish a connection between the Unique Games
Conjecture and the problem of approximating the expansion profile of
graphs. In particular, we show that the Unique Games Conjecture is
true if the expansion of small sets in graphs is hard to approximate
in a certain regime. This result provides the first non-trivial
sufficient condition for the truth of the conjecture. (Previously,
only implications of the truth of the conjecture were known.)
Based on joint works with Prasad Raghavendra.
More information about the talks
mailing list