论文标题
$ 4/3 $ - Approximation算法，最低$ 2 $ - 边缘连接的多纸在半综合案例中
A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case
论文作者
论文摘要
给定$ n $顶点上的连接的无向图$ \ bar {g} $，而非负边成本$ c $，2欧元的问题是找到$ 2 $ -EDGE〜连接的最低成本的$ \ bar {g} $的连接。 2ECM的天然线性程序（LP）与$ \ bar {g} $的度量封闭情况下的旅行推销员问题相吻合，给出了最佳成本的下限。对于该LP通过半综合解决方案$ x $优化的实例，Carr and Ravi（1998）表明，整数差距最多是$ \ frac43 $：他们表明矢量$ \ frac43 x $占主导地位的发射量组合，$ 2 $ - edge contence contence contence contence contence contence contence contence contence contence contence contence contence contence contence contence contence contency spanning spanning multiSubgraph的$ \ bar。 通过应用Lovász的分裂定理，我们为由于Carr和Ravi的结果提供了更简单的证明。我们的证明自然会导致$ \ frac43 $ - approximation算法，用于半整合实例。给定2磅的LP的半集体解决方案$ x $，我们给出了$ O（n^2）$ - 时间算法，以获得$ 2 $ - 边缘连接的跨度$ \ bar {g} $，其成本最多为$ \ frac43 c^t x $。
Given a connected undirected graph $\bar{G}$ on $n$ vertices, and non-negative edge costs $c$, the 2ECM problem is that of finding a $2$-edge~connected spanning multisubgraph of $\bar{G}$ of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of $\bar{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of $2$-edge connected spanning multisubgraphs of $\bar{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovász's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for 2ECM, we give an $O(n^2)$-time algorithm to obtain a $2$-edge connected spanning multisubgraph of $\bar{G}$ whose cost is at most $\frac43 c^T x$.
