scientific article; zbMATH DE number 7205039
From MaRDI portal
Publication:5111750
DOI10.4230/LIPIcs.ESA.2017.61zbMath1442.68181MaRDI QIDQ5111750
Publication date: 27 May 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
approximation algorithmintegrality gaptree augmentationhalf-integral extreme pointslogarithmic costs
Trees (05C05) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (9)
Flexible Graph Connectivity ⋮ A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ LP-relaxations for tree augmentation ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ 2-node-connectivity network design ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints ⋮ Flexible graph connectivity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Covering a laminar family by leaf to leaf links
- On the integrality ratio for tree augmentation
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Approximating (unweighted) tree augmentation via lift-and-project. II
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\)
- Iterative Methods in Combinatorial Optimization
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- LP-Relaxations for Tree Augmentation.
- Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
- Parameterized Algorithms
This page was built for publication:
