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 0(n), although our algorithms solve most of these problems so long as the average degree is 0(n). Denseness for nongraph 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. ] 1999 Academic Press polynomial time for some fixed $>0. (More recently, Ha# stad [H96] showed that if SAT does not have randomized polynomial-time algorithms, then CLIQUE cannot be approximated to within a factor n 1&$ for every $>0.) Others problems, such as those related to graph separators [LR88], have algorithms with approximation ratios close to O(log n). No inapproximability results are known for them. MAX-SNP problems, such as MAX-CUT or MAX-3-SAT, can be approximated to within some fixed constant factor but no better [PY91, ALM + 92]. Only a few problems, such as KNAPSACK [S75] and BIN PACKING [FL81], are known to have polynomial time approximation schemes (PTASs). A PTAS is an algorithm that, for every fixed =>0, achieves an approximation ratio of 1+= in time that is polynomial in the input size (but could grow very fast with 1ร=, such as O(n 1ร= )). A PTAS thus allows us to trade off approximation accuracy for running time. (In the previous definition, if the running time is polynomial in 1ร= as well, then we have a fully polynomial time approximation scheme. These are known to exist for a few problems [GJ79, DFK91, KLM89].) Unfortunately, recent results [ALM + 92] show that if P{NP, then PTASs do not exist for many NP-hard problems. In particular, this is is true for every MAX-SNP-hard problem. (The class of MAX-SNPhard problems includes VERTEX COVER, MAX-3-SAT, MAX-CUT, METRIC TSP, MULTIWAY CUTS, and many others [PY91].)
Note that the inapproximability results mentioned above, like all NP-hardness results, rule out approximation only on worst-case instances of the problem. They do not rule out the existence of algorithms (heuristics) that do well on most instances. This observation is the starting point of our research.
This paper gives PTASs for a large class of NP-hard problems when the problem instance is dense. The definition of denseness depends on the problem; for example, dense graphs are graphs with 0(n 2 ) edges while dense 3-SAT