Polynomial time approximation schemes for dense instances of NP-hard problems

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 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 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 smooth integer programs, where the objective function and the constraints are "dense" polynomials of constant degree. (C) 1999 Academic Press.