The regularity lemma and approximation schemes for dense problems
The regularity lemma and approximation schemes for dense problems
复制标题
稠密问题的正则引理和近似方案
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. Kannan
中科院分区：
文献类型：
--
作者：
A. Frieze;R. Kannan
本文有两个主要贡献。首先，我们利用正则引理的构造性版本，针对稠密图中的几个图“细分”问题直接给出简单的多项式时间近似方案，这些问题包括最大割问题、图二分问题、最小l - 路割问题以及图分隔问题。阿罗拉（Arora）、卡格尔（Karger）和卡尔平斯基（Karpinski）（1992年）针对这些问题给出了首个多项式时间近似方案，其运行时间为\(O(n^{o(1 / \epsilon^{2})})\)。我们的多项式时间近似方案的运行时间中\(n\)的指数是一个与\(\epsilon\)无关的常数。这里的核心要点是正则引理解释了为什么这些最大 - SNP困难问题在稠密图中变得容易。我们还针对二次分配问题（QAP）的一个特殊情况的稠密版本给出了一个简单的多项式时间近似方案。
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).