On the integrality ratio for tree augmentation

DOI10.1016/j.orl.2008.01.009zbMath1155.90466OpenAlexW2002923907MaRDI QIDQ1003482

Joseph Cheriyan, Jochen Könemann, Rohit Khandekar, Howard J. Karloff

Publication date: 4 March 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2008.01.009

zbMATH Keywords

linear programminginteger programmingconnectivity augmentationtree augmentation2-edge-connected graphintegrality ratio

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Linear programming (90C05)

Related Items (24)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On the tree augmentation problem ⋮ A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ LP-relaxations for tree augmentation ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Approximating (unweighted) tree augmentation via lift-and-project. II ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ 2-node-connectivity network design ⋮ Covering a laminar family by leaf to leaf links ⋮ Unnamed Item ⋮ Cut Dominants and Forbidden Minors ⋮ A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ On small-depth tree augmentations ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ 2-node-connectivity network design

Cites Work

• Minimum-weight two-connected spanning networks
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Unnamed Item

This page was built for publication: On the integrality ratio for tree augmentation