TY - JOUR

T1 - Polynomial time approximation schemes for dense instances of script N ℘-hard problems

AU - Arora, Sanjeev

AU - Karger, David

AU - Karpinski, Marek

N1 - Funding Information:
4Supported in part by the International Computer Science Institute, 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. E-mail: marek cs.bonn.edu.
Funding Information:
2Supported by an NSF CAREER Award NSF CCR-9502747 and an Alfred Sloan Fellowship. E-mail: arora cs.princeton.edu.

PY - 1999/2

Y1 - 1999/2

N2 - We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many script N sign script P sign-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 Ω(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 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.

AB - We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many script N sign script P sign-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 Ω(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 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.

UR - http://www.scopus.com/inward/record.url?scp=0033077325&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033077325&partnerID=8YFLogxK

U2 - 10.1006/jcss.1998.1605

DO - 10.1006/jcss.1998.1605

M3 - Article

AN - SCOPUS:0033077325

VL - 58

SP - 193

EP - 210

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 1

ER -