On the integrality ratio for tree augmentation
From MaRDI portal
Recommendations
Cites work
- A factor 2 approximation algorithm for the generalized Steiner network problem
- scientific article; zbMATH DE number 1405806 (Why is no real title available?)
- Minimum-weight two-connected spanning networks
- Survivable networks, linear programming relaxations and the parsimonious property
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
Cited in
(31)- 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
- 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
- A simple LP-based approximation algorithm for the matching augmentation problem
- Shorter tours and longer detours: uniform covers and a bit beyond
- On the cycle augmentation problem: hardness and approximation algorithms
- On the tree augmentation problem
- Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
- Cut dominants and forbidden minors
- A (1 + 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- scientific article; zbMATH DE number 7205039 (Why is no real title available?)
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- Node connectivity augmentation via iterative randomized rounding
- On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
- 2-node-connectivity network design
- A (1.5+)-approximation algorithm for weighted connectivity augmentation
- Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
- Approximation algorithms for node and element connectivity augmentation problems
- Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
- Approximation algorithms for Steiner connectivity augmentation
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- Covering a laminar family by leaf to leaf links
This page was built for publication: On the integrality ratio for tree augmentation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003482)
