
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1994  Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V  
85119

Polynomial Time Approximation Schemes for Dense Instances of NPHard 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 3satisfiability. 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 nongraph 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
English 
Universität Bonn > Institut für Informatik > Abteilung V 