Approximate solutions to NP-hard problems

It is a fact of life that most interesting optimization problems are NP-hard. One way to cope with this intractability is to look for efficient (polynomial time) algorithms that produce solutions with guaranteed performance with respect to the optimum solution (eg. is off by at most 25%, or by a factor of 10, etc.) While the complexity of finding exact solutions of all NP-complete problems is the same up to polynomial factors, this elegant unified picture disappers rather dramatically when one considers approximate solutions. For example, while vertex cover and independent set are both the same problems for exact solutions, the former has a simple factor 2 approximation algorithm (that delivers a solution with at most twice as many nodes as the minimum vertex cover), while the latter has been shown to be hard to approximate within any reasonable factor. The lack of a unified picture in turns makes the pursuit of understanding and classifying problems based on their approximability an intriguing one with diverse techniques used for studying different problems.

Ideally, for a problem at hand, we would like to have an approximation algorithm with provable performance ratio together with a matching hardness result showing that this ratio cannot be improved (assuming, for example, that P doesn't equal NP). Remarkable progress in this area over the past decade has now culminated in such results for several fundamental problems, including 3SAT, 3LIN (linear equations mod 2), Set Cover (the greedy algorithm is known to be essentially the best possible), and Independent Set. The main tool to demonstrate hardness of approximation results has been Probabilistically Checkable Proofs (PCP), which provide a way to present NP witnesses so that they can be verified by looking at very few bits. The study of PCP is interesting in its own right and in addition optimizing different parameters in the proof system leads to better inapproximability results for various problems.

We have investigated the approximability of several fundamental problems, including coloring graphs with small chromatic number, coloring hypergraphs, set splitting, finding edge-disjoint paths in directed graphs, 2-ary constraint satisfaction problems, etc. Most recently, we obtained a near-tight hardness result for vertex cover on K-uniform hypergraphs (or equivalently, hitting set with sets of size K) where one is a given a collection of K-element subsets from a universe and the goal is to pick the fewest number of elements from the universe so that each subset contains at least one of the picked elements. A simple algorithm is known to achieve a factor of K, and we showed that doing better than a factor (K-1) is NP-hard.

There are numerous other problems, especially in graph theory and certain constraint satisfaction problems, whose approximability is, despite all this progress, very poorly understood (more often from the hardness side). Some of our favorite ones include Max Cut, Edge-disjoint paths on undirected graphs, Multiway Cut, Bipartite Clique, Coloring 3-colorable graphs, etc. Much progress remains to be made in this area!

Sample papers