On the Tree Augmentation Problem
- PDF / 526,077 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 259 Views
On the Tree Augmentation Problem Zeev Nutov1 Received: 7 December 2018 / Accepted: 1 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In the Tree Augmentation problem we are given a tree T = (V , F) and a set E ⊆ V × V of edges with positive integer costs {ce : e ∈ E}. The goal is to augment T by a minimum cost edge set J ⊆ E such that T ∪ J is 2-edge-connected. We obtain the following results. – Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost M of an edge in E is bounded by a constant; his algorithm computes a 1.96418 + 2 O(1)
approximate solution in time n (M/ ) . Using a simpler LP, we achieve ratio 12 O(M/ 2 ) poly(n). This gives ratio better than 2 for logarithmic 7 + in time 2 costs, and not only for constant costs. – One of the oldest open questions for the problem is whether for unit costs (when M = 1) the standard LP-relaxation, so called Cut- LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut- LP is at most 28/15 = 2 − 2/15. In addition, we will prove that another natural LP-relaxation, that is much simpler than the ones in previous work, has integrality gap at most 7/4. Keywords Tree augmentation · Approximation algorithm · Extreme points · Integrality gap
1 Introduction We consider the following problem:
A preliminary version appeared in ESA 2017: 61:1-61:14.
B 1
Zeev Nutov [email protected] Department of Mathematics and Computer Science, The Open University of Israel, Raanana, Israel
123
Algorithmica
Tree Augmentation Input: A tree T = (V , F) and an additional set E ⊆ V × V of edges with positive integer costs c = {ce : e ∈ E}. Output: A minimum cost edge set J ⊆ E such that T ∪ J is 2-edgeconnected. The problem was studied extensively, c.f. [5–7,9,12,13,15,21–23,25,27]. For a long time the best known ratio for the problem was 2 for arbitrary costs [15] and 1.5 for unit costs [12,23]; see also [13] for a simple 1.8-approximation algorithm. It is also known that the integrality gap of a standard LP-relaxation for the problem, so called Cut- LP, is at most 2 [15] and at least 1.5 [7]. Several other LP and SDP relaxations were introduced to show that the algorithm in [12,13,23] achieves ratio better than 2 w.r.t. to these relaxations, c.f. [5,22]. For additional algorithms with ratio better than 2 for restricted versions see [9,25]. Let M denote the maximum cost of an edge in E. Recently Adjiashvili [1] introduced a novel LP for the problem—so called the k- Bundle- LP, and used it to break the natural 2-approximation barrier for instances when M is bounded by a constant. To introduce this result we need some definitions. The edges of T will be called T -edges to distinguish them from the edges in E. Tree Augmentation can be formulated as a problem of covering the T -edges by paths. Let Tuv denote the unique uv-path in T . We say that an edge uv covers a T -edge f
Data Loading...
