In the 1990ies there was
a revolution in our understanding of the approximability
of NP-hard combinatorial optimization problems.
To a large extent this was the consequence of
introducing new techniques for proving hardness of approximation.
The FGLSS paper helped start it all.
Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra and Mario
Szegedy.
Interactive Proofs and the Hardness of Approximating Cliques.
Journal of the ACM, Vol. 43, No. 2, March 1996, pp. 268--292.
The relation to approximation of NP-hard optimization problems
made the study of interactive proofs and their variants a main-stream
research area.
Much of my work on the theory of interactive proofs is related to error
reduction for two-prover one-round proof systems. References to this work
can be found in the following survey.
Uriel Feige.
Error reduction by parallel repetition -- the state of the art.
Technical report CS95-32 of the Weizmann Institute, 1995.
The Lovasz theta function was conjectured to approximate the size of the
maximum independent set within a ratio of $O(\sqrt n)$.
The following paper refutes this conjecture.
Uriel Feige.
Randomized Graph Products, Chromatic Numbers, and the
Lovasz theta Function.
Combinatorica 17 (1) 79--90, 1997.
Goemans and Williamson introduced the random hyperplane rounding technique for semidefinite programming, and obtained an approximation ratio of roughly 0.87856 for MAX CUT. The following paper shows some of the difficulties involved in improving the approximation ratio.
Uriel Feige and Gideon Schechtman.
On the optimality of the random hyperplane rounding technique for MAX CUT.
To appear in Random Structures and Algorithms.
The following two papers present essentially best possible hardness of
approximation results for two central problems.
Uriel Feige.
A Threshold of ln n for Approximating Set Cover.
Journal of the ACM, 45(4), 634--652, July 1998.
Uriel Feige and Joe Kilian.
Zero Knowledge and the Chromatic Number.
Journal of Computer and System Sciences, 57(2), 187--199, October 1998.
Now to some positive results. My first paper on approximation algorithms was
written while I was still under the influence of two prover proof systems.
(In fact, also the FGLSS paper and the set cover paper started from
observations that came up
while studying parallel repetition of two prover proof systems.)
Uriel Feige and Michel Goemans.
Approximating the value of two prover proof systems,
with applications to MAX 2SAT and MAX DICUT.
Proc. of 3rd Israel Symposium on the Theory of Computing and
Systems, 182--189, 1995.
The following survey includes some research directions I have been playing
with. (However, the paper with Schechtman, referred to above, later showed
that some of these directions are not as promising as I initially hoped.)
Uriel Feige.
Randomized rounding of semidefinite programs -- variations on the MAX CUT
example.
Randomization, Approximation, and Combinatorial Optimization,
Proceedings of Random-Approx'99,
Lecture Notes in Computer Science 1671, Springer 1999, 189--196.
Despite the great advances in our understanding of approximability of
NP-hard combinatorial optimization problems, for some well known
problems there still remain huge gaps in our knowledge.
This motivated the following two papers.
Uriel Feige.
Approximating the bandwidth via volume respecting embeddings.
Journal of Computer and System Sciences, 60(3), 510--539, June 2000.
Uriel Feige and Robert Krauthgamer.
A polylogarithmic approximation of the minimum bisection.
SIAM Journal on Computing, 31(4): 1090--1118 (2002).
Realizing that some problems are immune against approximation algorithms,
we seek other ways of coping with NP-hardness.
Uriel Feige and Joe Kilian.
Heuristics for semirandom graph problems.
Journal of Computer and System Sciences, 63, 639--671 (2001).
Good approximation
algorithms can often serve as heuristics that work well on average. This
is the topic of the following paper.
Uriel Feige.
Relations between average case complexity and approximation
complexity.
Proceedings of 34th STOC, 2002,
534--543.