Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1994 Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
Sanjeev Arora, David Karger, Marek Karpinski
[Download PostScript] [Download PDF]

We present a unified framework for designing polynomial time approximation schemes (PTASs) for `dense'' instances of many $\NP$-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum $k$-way cut with and without specified sources, and maximum 3-satisfiability. Dense graphs for us are graphs with minimum degree $\Theta(n)$, although some of our algorithms work so long as the graph is dense `on average''. (Denseness for non-graph problems is defined similarly.) The unified framework begins with the idea of {\em exhaustive sampling:} picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certain {\em smooth\/} integer programs where the objective function is a `dense'' polynomial of constant degree.

Last Change: 11/05/14 at 09:50:14
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope