Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation

DOI10.1137/151004288zbMath1345.90074arXiv1409.5561OpenAlexW1557201898MaRDI QIDQ2804546

Takuro Fukunaga

Publication date: 29 April 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

survivable network designmultiflowterminal backup

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Improved approximation algorithms for minimum power covering problems

Cites Work

• Unnamed Item
• Network design via iterative rounding of setpair relaxations
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Minimum cost multiflows in undirected networks
• Minimum weight \((T,d)\)-joins and multi-joins
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Min-cost multiflows in node-capacitated undirected networks
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• The Generalized Terminal Backup Problem
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Terminal Backup, 3D Matching, and Covering Cubic Graphs
• On some connectivity properties of Eulerian graphs

This page was built for publication: Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation