The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. These results prove that the smallest k-ECSS problem gets easier to approximate as k tends to infinity. They also show the integrality gap of the natural linear program is at most 1 + 2/k, for both directed and undirected graphs.
展开▼
机译：给定一个图和一个整数 k ，最小的k-ECSS问题找到一个 k 边连接并且包含的跨度子图尽可能少的边数。我们研究了基于四舍五入的LP解的自然近似算法。对于无向图，其中 k > 1奇数，对于无向图，近似率的严格边界为1 + 3 / k 偶数为 k 的图形，而任意 k 为有向图的图形为1 + 2 / k 。使用迭代舍入可以将第一个上限提高到1 + 2 / k 。这些结果证明，随着 k 趋于无穷大，最小的 k -ECSS问题变得更容易近似。他们还表明，对于有向图和无向图，自然线性程序的积分缺口最大为1 + 2 / k 。
展开▼
