论文标题
对称的线性编程公式，用于最低限度的剪切，并应用于TSP
Symmetric Linear Programming Formulations for Minimum Cut with Applications to TSP
论文作者
论文摘要
我们引入了多个对称LP松弛，以解决最小的剪切问题。当输入是哈密顿周期时，放松将提供最佳和近似的解决方案。我们表明，这导致了两个有趣的结果之一。在一种情况下，这些LP始终提供最佳且接近最佳的解决方案，然后对于所考虑的问题，它们将是最小的已知对称LP。否则，这些LP配方与子三次放松相比，严格为旅行销售人员问题提供了更好的LP放松。我们具有最小的已知LP公式，该公式是9/8的approximation或更高的最低速率。此外，本文研究的最小切割的LP松弛具有有趣的限制。 LP仅包含一个典型的最小限制，所有其他约束通常仅用于最大切割放松。
We introduce multiple symmetric LP relaxations for minimum cut problems. The relaxations give optimal and approximate solutions when the input is a Hamiltonian cycle. We show that this leads to one of two interesting results. In one case, these LPs always give optimal and near optimal solutions, and then they would be the smallest known symmetric LPs for the problems considered. Otherwise, these LP formulations give strictly better LP relaxations for the traveling salesperson problem than the subtour relaxation. We have the smallest known LP formulation that is a 9/8-approximation or better for min-cut. In addition, the LP relaxation of min-cut investigated in this paper has interesting constraints; the LP contains only a single typical min-cut constraint and all other constraints are typically only used for max-cut relaxations.
