Polynomial Time Approximation Schemes for Dense Instances of $NP$-HardProblems
Title | Polynomial Time Approximation Schemes for Dense Instances of $NP$-HardProblems |
Publication Type | Technical Report |
Year of Publication | 1995 |
Authors | Arora, S., Karger D. R., & Karpinski M. |
Other Numbers | 951 |
Abstract | 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 sources, and maximum 3-satisfiability. Dense graphs for us are graphs with minimum degree ?(n), although some of our algorithms work so long as the graph is dense "on average." (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 is a "dense" polynomial of constant degree. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-95-011.pdf |
Bibliographic Notes | ICSI Technical Report TR-95-011 |
Abbreviated Authors | S. Arora, D. Karger, and M. Karpinski |
ICSI Publication Type | Technical Report |