Coping with NP-hardness

References to some of my work on this subject appear below. The links included are to personal copies (ps files) of these papers on my home machine. These links do not lead to the respective journal/conference proceedings. You are expected to respect all relevant copyright laws.

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.