论文标题
梳理不平等的典型欧几里得TSP实例
Comb inequalities for typical Euclidean TSP instances
论文作者
论文摘要
我们证明，即使在平均情况下，欧几里得旅行推销员问题也表现出$（1+ε）$ $ε> 0 $的完整性差距为$（1+ε）$，当时所有有限尺寸的梳子不平等增加了持有的KARP线性编程放松。这意味着，即使是随机输入，大量的分支和切割算法也需要欧几里得TSP的指数时间。
We prove that even in average case, the Euclidean Traveling Salesman Problem exhibits an integrality gap of $(1+ε)$ for $ε>0$ when the Held-Karp Linear Programming relaxation is augmented by all comb inequalities of bounded size. This implies that large classes of branch-and-cut algorithms take exponential time for the Euclidean TSP, even on random inputs.
