论文标题
KARP在密集的挖掘上的修补算法
Karp's patching algorithm on dense digraphs
论文作者
论文摘要
我们考虑以下问题。我们获得了一个密集的挖掘$ D $，至少$αn$，其中$α> 1/2 $是一个常数。 $ d $的边缘给出了边缘成本$ c（e），e（d）$中的e \，其中$ c（e）$是统一$ [0,1] $随机变量$ u $的独立副本。令$ 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$ with minimum in- and out-degree at least $αn$, where $α>1/2$ is a constant. The edges of $D$ are given edge costs $C(e),e\in E(D)$, where $C(e)$ is an independent copy of the uniform $[0,1]$ random variable $U$. 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 that is asymptotically equal to that of the associated assignment problem. Karp's algorithm runs in polynomial time.
