Approximating the generalized terminal backup problem via half-integral multiflow relaxation

DOI10.1137/151004288MaRDI QIDQ2804546zbMATH OpenOpenAlexFDO

Authors 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, https://drops.dagstuhl.de/opus/volltexte/2015/4923/

zbMATH Keywords

survivable network designmultiflowterminal backup

Mathematics Subject Classification ID

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

Abstract: We consider a network design problem called the generalized terminal backup problem. Whereas earlier work investigated the edge-connectivity constraints only, we consider both edge- and node-connectivity constraints for this problem. A major contribution of this paper is the development of a strongly polynomial-time 4/3-approximation algorithm for the problem. Specifically, we show that a linear programming relaxation of the problem is half-integral, and that the half-integral optimal solution can be rounded to a 4/3-approximate solution. We also prove that the linear programming relaxation of the problem with the edge-connectivity constraints is equivalent to minimizing the cost of half-integral multiflows that satisfy flow demands given from terminals. This observation presents a strongly polynomial-time algorithm for computing a minimum cost half-integral multiflow under flow demand constraints.

Recommendations

• Approximating the generalized terminal backup problem via half-integral multiflow relaxation
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• The generalized terminal backup problem
• The generalized terminal backup problem
• Minimum cost multiflows in undirected networks

Cites work

• scientific article; zbMATH DE number 3550435 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Min-cost multiflows in node-capacitated undirected networks
• Minimum cost multiflows in undirected networks
• Minimum weight \((T,d)\)-joins and multi-joins
• Network design via iterative rounding of setpair relaxations
• On some connectivity properties of Eulerian graphs
• Terminal backup, 3D matching, and covering cubic graphs
• The generalized terminal backup problem

Cited in

(7)

• Discrete convex functions on graphs and their algorithmic applications
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• The generalized terminal backup problem
• The generalized terminal backup problem
• Improved approximation algorithms for minimum power covering problems
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Approximating the generalized terminal backup problem via half-integral multiflow relaxation

This page was built for publication: Approximating the generalized terminal backup problem via half-integral multiflow relaxation

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