The regularity lemma and approximation schemes for dense problems
Authors:
- A. FriezeAFA. Frieze
- R. KannanRKR. Kannan
- 24 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 16 (02725428) , 12-20
Abstract
There are two main contributions of the present paper. In the first, we use the constructive version of the Regularity Lemma to give directly simple polynomial time approximation schemes for several graph "subdivision" problems in dense graphs including the Max Cut problem, the Graph Bisection problem, the Min l-way cut problem and Graph Separator problem. Arora, Karger and Karpinski (1992) gave the first PTASs for these problems whose running time is O(n/sup o(1/e2)/). Our PTASs have running time where the exponent of n is a constant independent of e. The central point here is that the Regularity Lemma provides an explanation of why these Max-SNP hard problems turn out to be easy in dense graphs. We also give a simple PTAS for dense versions of a special case of the Quadratic Assignment Problem (QAP).Keywords
This publication has 13 references indexed in Scilit:
- Approximately Counting Hamilton Paths and Cycles in Dense GraphsSIAM Journal on Computing, 1998
- MAX-CUT has a randomized approximation scheme in dense graphsRandom Structures & Algorithms, 1996
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense caseRandom Structures & Algorithms, 1995
- Polynomial time approximation schemes for dense instances of NP-hard problems1995
- The quadratic assignment problem: A survey and recent developments1994
- The Uniformity Lemma for hypergraphsGraphs and Combinatorics, 1992
- Proof verification and hardness of approximation problems1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Approximating the PermanentSIAM Journal on Computing, 1989
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976