Approximation schemes for densi instances of np-hard problems

Polynomial Time Approximation Schemes for Dense Instances of N P-Hard Problems
Sanjeev Arora∗ David Karger† Marek Karpinski‡

Abstract We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense” instances of many N P-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specifiedterminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree Ω(n), although our algorithms solve most of these problems so long as the average degree is Ω(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 thenusing 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.

1

Introduction

Approximation algorithms, whenever they can be found, are a way to deal with the N Phardness of optimization problems.Ideally, they should run in polynomial time and have a small approximation ratio, which is the worst-case ratio of the value of the solution returned by the algorithm to the value of the optimum solution. (This definition is for minimization problems; for maximization problems the ratio is inverted so that it is always at least 1.) Optimization problems seem to be approximable to different degrees (see[Shm94] for a survey). We know that unless P = N P, problems such as CLIQUE [FGL+ 91, AS92, ALM+ 92] and CHROMATIC NUMBER [LY93] cannot be approximated even to within a factor of nδ in polynomial time, for some fixed δ > 0. (More recently, H˚ astad [H96] showed that if SAT does not have randomized polynomial-time algorithms, then CLIQUE cannot be approximated to within a factor n1−δ , 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-SN P 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 havepolynomial 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(n1/ǫ )). 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∗ Princeton University. Supported by an NSF CAREER Award NSF CCR-9502747 and an Alfred Sloan Fellowship. email: arora@cs.princeton.edu. URL: http://www.cs.princeton.edu/~arora † MIT Laboratory for Computer Science. Work done at AT&T Bell Laboratories. email: karger@lcs.mit.edu URL: http://theory.lcs.mit.edu/~karger ‡ University of Bonn. Supported in part by the International Computer ScienceInstitute, Berkeley, California, by the DFG Grant KA 673/4-1, ESPRIT BR Grants 7097, 21726, and EC-US 030, and by the Max-Planck Research Prize. Email: marek@cs.bonn.edu , URL: http://theory.cs.uni-bonn.de/~marek.

1

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 N P-hard problems. In particular, this is is true for every MAX-SN P-hard problem. (The class of MAX-SN P-hard problems includes VERTEX COVER, MAX-3SAT, MAX-CUT, METRIC TSP, MULTIWAY CUTS, and many others [PY91].) Note that the inapproximability results mentioned above, like all N P-hardness results, rule out approximation only on worst case instances of the...