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 8922 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  English Universität Bonn -> Institut für Informatik -> Abteilung V