[talks] R Manokaran general exam
Melissa M Lawson
mml at CS.Princeton.EDU
Tue Apr 29 13:26:59 EDT 2008
Rajsekar Manokaran will present his research seminar/general exam on Monday May 5
at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor),
Moses Charikar, and Boaz Barak. Everyone is welcome to attend his talk, and those
faculty wishing to remain for the oral exam following are welcome to do so. His abstract
and
reading list appear below.
Abstract
--------
Mathematical relaxations are one of the most powerful tools used in designing
approximation algorithms for hard combinatorial optimization problems. For example,
linear programming relaxations have provided
the best approximation algorithms known for a huge number of
optimization problems. More recently, for some optimization problems,
semidefinite relaxations have been used to obtain breakthrough
improvements in the approximation factor. This work investigates the limits on
approximations achieved by mathematical relaxations of
combinatorial optimization problems and their relation to the
computation hardness of approximating them.
For a small yet quite general set of problems, a direct way to convert integrality gaps
for a linear programming relaxation of the problem into a computational hardness
result under a certain conjecture is shown. This problem, known as metric labeling is
a generalization of classification problems with pairwise constraints. In this work, it
is shown that a certain linear programming relaxation gives the best approximation one
can expect, assuming the unique games conjecture.
Continuing in the same theme, a similar computational hardness result is shown for the
maximum acyclic subgraph problem. Here, a trivial
algorithm obtains a half approximation and obtaining a better
approximation algorithm has been an open problem for quite some time.
Assuming the UG conjecture, this work shows that it is computationally hard to approximate
the maximum acyclic subgraph problem by a better factor is hard. This result also,
unconditionally, rules out a simple semi-definite programming approach to obtain a better
approximation.
Reading List
------------
1. Complexity Theory: A Modern Approach
by Sanjeev Arora and Boaz Barak
Chapters 1-8, 16-19.
2. Approximation Algorithms
by Vijay Vazirani
Chapters 1-4, 12-21.
3. Expander Flows, Geometric Embeddings, and Graph Partitionings
by Sanjeev Arora, Satish Rao, and Umesh Vazirani
ACM Symposium on Theory of Computing, 2004.
4. A tight bound on approximating arbitrary metrics by tree metrics
by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar
ACM Symposium on Theory of Computing, 2003
5. Some Optimal Inapproximability Results
by Johan Hastad
STOC 1997.
6. Proving integrality gaps without knowing the linear program.
by Sanjeev Arora, Bela Bollobas and Laszlo Lovasz.
Proc. IEEE Foundations of Computer Science, 2002.
7. Local Global Tradeoffs in Metric Embeddings,
by Moses Charikar, Konstantin Makarychev, Yury Makarychev,
FOCS 2007, pp. 713-723.
8. On the power of unique 2-prover 1-round games
by Subhash Khot
STOC '02.
9. Optimal inapproximability results for max-cut and other 2-variable csps?
by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell.
FOCS '04.
10. The unique games conjecture, integrality gap for cut problems and
embeddability of negative type metrics into $L_1$.
by Subhash Khot and Nisheeth Vishnoi.
FOCS '05.
11. Noise stability of functions with low influences: Invariance and optimality.
by Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz.
FOCS '05.
12. Vertex cover might be hard to approximate to within 2-$\epsilon$.
by Subhash Khot and Oded Regev.
J. Comput. Syst. Sci.
13. Near-Optimal Algorithms for Unique Games,
by Moses Charikar, Konstantin Makarychev, Yury Makarychev,
STOC 2006, pp. 205-214.
14. Approximation algorithms for the metric labeling problem via a new linear
programming formulation.
Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor, and Leonid Zosin.
SIAM J. Disc. Math.
15. On the advantage over random for maximum acyclic subgraph.
Moses Charikar, Konstantin Makarychev, and Yury Makarychev.
FOCS 2007, pp. 625-633.
More information about the talks
mailing list