The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree @math , an additional set of edges @math disjoint from @math called , and a cost vector @math , WTAP asks to find a minimum-cost set @math with the property that @math is @math -edge connected. The special case where @math for all @math is called the Tree Augmentation Problem (TAP). Both problems are known to be NP-hard. For the class of bounded cost vectors, we present a first improved approximation algorithm for WTAP since more than three decades. Concretely, for any @math and @math we present an LP based @math -approximation for WTAP restricted to cost vectors @math in @math for @math . For the special case of TAP we improve this factor to @math . Our results rely on a new LP, that significantly differs from existing LPs achieving improved bounds for TAP. We round a fractional solution in two phases. The first phase uses the fractional solution to decompose the tree and its fractional solution into so-called @math -simple pairs losing only an @math -factor in the objective function. We then show how to use the additional constraints in our LP combined with the @math -simple structure to round a fractional solution in each part of the decomposition.
WTAP can also be interpreted as a problem of covering a laminar family with point-to-point links (see e.g. @cite_8 ). This observation implies that the problem of augmenting a @math -edge connected graph to a @math -edge connected graph can be reduced to WTAP, whenever @math is odd, due to the laminar structure of the family of minimum cuts, in this case.
@cite_8
2541541317
In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7 4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case.