## 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.)