Rajsekar Manokaran will present his preFPO on Wednesday March 28
at 1:30PM in Room 402. The members of his committee are: Sanjeev
Arora, advisor; Moses Charikar and Zeev Dvir, readers; Mark
Braverman and Bernard Chazelle, nonreaders. Everyone is invited
to attend his talk. His abstract follows below.
-------------------
Title: Approximability using Mathematical Relaxations
A standard approach to coping with the NP-hardness of a combinatorial
optimization problem involves designing algorithms that guarantee a
solution within a factor p of the optimum (a.k.a an p-approximation
algorithm). We study the approximability of various fundamental graph
optimization problems using linear programming~(LP) relaxations.
In the first part of the thesis, we study simple LP relaxations for
Metric Labeling, and a variety of Packing and Covering problems. For
all these problems, we show that the relaxation already obtains the
best approximation, upto known algorithmic barriers. The novelty here
is the generality of the technique: the proof only uses simple "local"
properties of the relaxation, oblivious of the actual approximation
factor, p, obtained thus.
In the second part, we use insights obtained from the above in
studying the approximability of a large class of ordering problems,
including the Maximum Acyclic Subgraph problem. Here, we show that a
trivial algorithm, that outputs a random ordering irrespective of the
instance in hand, already achieves the best appromximation factor upto
known algorithmic techniques.
In the final part, we study implications of "average-case" algorithmic
barriers. In particular, we show that the densest-k-subgraph problem
is hard to approximate to within any constant factor assuming random
k-AND formulas are hard to distinguish from well satisfiable ones.
These results are based on joint works with Noga Alon, Sanjeev Arora,
Moses Charikar, Venkatesan Guruswami, Johan Hastad, Amit Kumar, Dana
Moshkovitz, Joseph Naor, Prasad Raghavendra, Roy Schwartz, Madhur
Tulsiani, Nisheeth Vishnoi and Omri Weinstein