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

DOI10.1137/151004288zbMATH Open1345.90074arXiv1409.5561OpenAlexW1557201898MaRDI QIDQ2804546FDOQ2804546

Takuro Fukunaga

Publication date: 29 April 2016

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

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.

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

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

zbMATH Keywords

survivable network designmultiflowterminal backup

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)