DIMACS Princeton Theory Seminar
Title:
Non-Approximability Results for MAX SNP -- Towards Tight Results
Speaker:
- Oded Goldreich
- Weizmann Institute of Science
- Israel
Place:
- Room 402, Computer Science Building
- 35 Olden Street
- Princeton University.
Time:
- 12:05 PM (Lunch will be served at 11:45 AM)
- Friday, April 19, 1996
Abstract:
The state-of-the art with respect to the non-approximability
of MAX SNP hard problems has been steadily improving over
the last few years. In combination with the development of
new techniques for positive results on approximation, the
lower bounds and upper bounds on the approximability of
several benchmark problems are already within sight of
each other and there's hope that they may get tighter.
An interesting feature of the negative results is that
while the analysis has gotten tighter, in many senses
it has gotten simpler and more general. At this stage
it is possible to see the tightness of almost all steps
of the analysis. In this talk we will attempt to
show all the ingredients leading to the current hardness
results for MAX SNP hard problems.
This is joint work with Mihir Bellare (UCSD) and Madhu Sudan (IBM).
This talk covers a portion of the work
titled ``Free bits, PCP and Non-approximability: Towards tight results''.
Previous talks on this work were concentrated on the Max Clique results.
Document last modified on April 16, 1996