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

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 ≤32+ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\le \frac{3}{2}+\epsilon $$\end{document}, where ϵ>0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon >0$$\end{document} can be any small constant. We obtain this result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee of (32+ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{3}{2}+\epsilon $$\end{document}) 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).

• Publication year

  2015

• Venue

  Algorithmica

• Publication date

  2015-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00453-017-0275-7arXiv 1507.01309
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2

  2015influential reference
• The Lasserre hierarchy in Approximation algorithms Lecture Notes for the MAPSP 2013 Tutorial Preliminary version

  2013cited by this paper
• Directed Steiner Tree and the Lasserre Hierarchy

  2011influential reference
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

  2010cited by this paper
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

  2009influential reference
• On the integrality ratio for tree augmentation

  2008cited by this paper
• Hardness of Approximation for Vertex-Connectivity Network Design Problems

  2002cited by this paper
• A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set

  2001influential reference
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree

  1999influential reference
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

  1998cited by this paper
• Graph Theory

  1997cited by this paper
• Approximation Algorithms for Several Graph Augmentation Problems

  1981cited by this paper

• A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing

  2026cites this paper
• Approximation Schemes for Planar Graph Connectivity Problems

  2025cites this paper
• A Better-Than-2 Approximation for the Directed Tree Augmentation Problem

  2025cites this paper
• Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree

  2025cites this paper
• 3/2-Approximation for the Forest Augmentation Problem

  2024cites this paper
• A 5/4-Approximation for Two-Edge Connectivity

  2024cites this paper
• Two-Edge Connectivity via Pac-Man Gluing

  2024influential citation
• A 4/3 Approximation for 2-Vertex-Connectivity

  2023cites this paper
• Node Connectivity Augmentation of Highly Connected Graphs

  2023influential citation
• Approximation Algorithms for Steiner Connectivity Augmentation

  2023cites this paper
• An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem

  2023cites this paper
• Improved Approximation for Two-Edge-Connectivity

  2022influential citation
• Finding Almost Tight Witness Trees

  2022cites this paper
• Choose your witnesses wisely

  2022cites this paper
• Matching Augmentation via Simultaneous Contractions

  2022cites this paper
• A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation

  2022cites this paper
• A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem

  2022cites this paper
• Better-than-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{4}{3}$$\end{document}43-approximations for leaf-to-l

  2022cites this paper
• Node connectivity augmentation via iterative randomized rounding

  2021cites this paper
• A Better-Than-2 Approximation for Weighted Tree Augmentation

  2021cites this paper
• Local Search for Weighted Tree Augmentation and Steiner Tree

  2021cites this paper
• Approximation Algorithms for Survivable Network Design

  2021cites this paper
• An Improved Approximation Algorithm for the Matching Augmentation Problem

  2020cites this paper
• Distributed Network Design

  2020cites this paper
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

  2020cites this paper
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree

  2019cites this paper
• On the Cycle Augmentation Problem: Hardness and Approximation Algorithms

  2019cites this paper
• Improved approximation for tree augmentation: saving by rewiring

  2018influential citation
• LP-Relaxations for Tree Augmentation

  2018influential citation
• Fast distributed approximation for TAP and 2-edge-connectivity

  2017cites this paper
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

  2017cites this paper
• On the Tree Augmentation Problem 1

  2017cites this paper
• Approximation Algorithms for Faster Communication and Cheaper Networks Using Linear Programming

  2017cites this paper
• 61 : 2 On the Tree Augmentation Problem

  2017cites this paper
• Coloring Down: $3/2$-approximation for special cases of the weighted tree augmentation problem

  2017cites this paper
• On the Tree Augmentation Problem

  2017cites this paper
• A 3/2-Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts

  2017cites this paper
• Improved Approximation for Weighted Tree Augmentation with Bounded Costs

  2016cites this paper
• Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations

  2015influential citation