The regularity lemma and approximation schemes for dense problems

摘要

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).