Approximating (unweighted) tree augmentation via lift-and-project. II

DOI10.1007/S00453-017-0275-7zbMATH Open1395.90233arXiv1507.01309OpenAlexW2963550906MaRDI QIDQ1709583FDOQ1709583

Authors: Joseph Cheriyan, Zhihan Gao 

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

Abstract: 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 $leqfrac32+epsilon$, where $epsilon>0$ can be any small constant. We obtain this result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee of ($frac32+epsilon$) 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, Mathieu and Nguyen (IPCO 2011).

Full work available at URL: https://arxiv.org/abs/1507.01309

Recommendations

• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• LP-relaxations for tree augmentation
• LP-relaxations for tree augmentation
• scientific article; zbMATH DE number 6850362
• Improved approximation for tree augmentation: saving by rewiring

zbMATH Keywords

linear programmingsemidefinite programmingapproximation algorithmsnetwork designgraph connectivityconnectivity augmentationlift-and-projectalgorithmic aspects of networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Graph theory
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On the integrality ratio for tree augmentation
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Integrality gaps of linear and semi-definite programming relaxations for knapsack

Cited In (16)

• Fast distributed approximation for TAP and 2-edge-connectivity
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• On the integrality ratio for tree augmentation
• On the tree augmentation problem
• Node connectivity augmentation via iterative randomized rounding
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A simple LP-based approximation algorithm for the matching augmentation problem
• A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On the cycle augmentation problem: hardness and approximation algorithms

This page was built for publication: Approximating (unweighted) tree augmentation via lift-and-project. II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709583)