Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1998 Copyright 1998 University of Bonn, Department of Computer Science, Abt. V
85195

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 terminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree $\Omega(n)$, although %\editsmall{some of our algorithms work}{our algorithms solve most of these problems so long as the average degree is $\Omega(n)$. 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 and the constraints are `dense'' polynomials of constant degree.

Last Change: 11/05/14 at 10:10:42
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V