Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II

作者：Cheriyan Joseph^*; Gao Zhihan

来源：Algorithmica, 2018, 80(2): 608-651.

DOI：10.1007/s00453-017-0275-7

• Approximation algorithms
• Lift-and-project
• Linear programming
• Semidefinite programming
• Network design
• Algorithmic aspects of networks
• Graph connectivity
• Connectivity augmentation

In Part II, we study the unweighted tree augmentation problem (TAP) via the Lasserre (sum of squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is , where can be any small constant. We obtain this result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee of () relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of integral solutions from the previous literature to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Karlin et al. (Integer Programming and Combinatorial Optimization, LNCS, volume 6655, Springer, pp 301-314, 2011).

• 出版日期2018-2