[talks] R Manokaran preFPO

[Melissa M. Lawson]

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