论文标题
KARP对密集挖掘的随机扰动的修补算法
Karp's patching algorithm on random perturbations of dense digraphs
论文作者
论文摘要
我们考虑以下问题。我们获得了一个密集的挖掘$ d_0 $，至少$αn$，其中$α> 0 $是一个常数。然后，我们将随机边缘$ r $添加到$ d_0 $中，以创建Digraph $ d $。在这里，边缘$ e $独立放置在$ r $的情况下，概率$ n^{--ε} $，其中$ε> 0 $是一个小的正常数。边缘$ e（d）$ d $的$ d $给出了独立边缘成本$ c = c（e），e（d）$中的e \，其中$ c $具有密度$ f（x）= a+bx+o（x）$ as $ x \ to $ x \ to 0 $。这里$ a> 0，b $是常数。主要示例将是统一的$ [0,1] $分布（$ a = 1，b = 0 $）和指数平均1分配$ exp（1）$（$ a = 1，b = -1 $）。令$ c（i，j），i，j \ in [n] $为关联的$ n \ times n $成本矩阵，其中$ c（i，j）= \ infty $如果$（i，j）\ notin e（d）$。我们表明，W.H.P. \ KARP的修补算法找到了不对称旅行销售人员问题的旅行，其成本在渐近上等于相关分配问题的成本。 KARP的算法在多项式时间内运行。
We consider the following question. We are given a dense digraph $D_0$ with minimum in- and out-degree at least $αn$, where $α>0$ is a constant. We then add random edges $R$ to $D_0$ to create a digraph $D$. Here an edge $e$ is placed independently into $R$ with probability $n^{-ε}$ where $ε>0$ is a small positive constant. The edges $E(D)$ of $D$ are given independent edge costs $C=C(e),e\in E(D)$, where $C$ has a density $f(x)=a+bx+o(x)$ as $x\to 0$. Here $a>0,b$ are constants. The prime examples will be the uniform $[0,1]$ distribution ($a=1,b=0$) and the exponential mean 1 distribution $EXP(1)$ ($a=1,b=-1$). Let $C(i,j),i,j\in[n]$ be the associated $n\times n$ cost matrix where $C(i,j)=\infty$ if $(i,j)\notin E(D)$. We show that w.h.p.\ the patching algorithm of Karp finds a tour for the asymmetric traveling salesperson problem whose cost is asymptotically equal to the cost of the associated assignment problem. Karp's algorithm runs in polynomial time.
