Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

We present a univied framework for designing Polynomial Time Approximation Schemes (PTASs) for "dense" instances of many NP- hard optimization problems, including graph maximum cut, graph bisection, all MAX-SNP problems (including MAX-3SAT), and minimum k-way cut with and without specified sources. Dense graphs for us are graphs with minimum degree THETA (n), although some algorithms work with weaker definitions of dense. (Denseness for non-graph problems is defined similarly.) The unified framework begins with the idea of exhaustive sampling: picking a small set of vertices, guessing where they go on the optimal solution, and then using their placement to determine the placement of everything else.