Sanjeev Arora

Princeton University

Approximation Schemes for Dense Instances of NP-hard Optimization Problems.

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

December 6, 1995 at 4:30 pm

Abstract:

It has recently been shown that for many NP-hard optimization problems (Clique, MAX-CUT, MAX-3SAT, etc.), computing good approximate solutions is also NP-hard.

This talk will show that many of these problems (including MAX-CUT, MAX-3SAT, MIN-BISECTION, MIN-LINEAR- ARRANGEMENT) are easy to approximate if the problem instance is ``dense." For instance, a graph on n vertices is dense if every vertex has degree O(n).

Some of the above results rely upon a new randomized rounding procedure for the assignment (or bipartite matching) problem, which is of independent interest.

(Based upon two papers, one joint work with D. Karger and M. Karpinski; the other with A. Frieze and H. Kaplan.)