Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems

DOI10.1016/S0167-6377(01)00094-3zbMath1018.90061OpenAlexW2018494567WikidataQ127063864 ScholiaQ127063864MaRDI QIDQ5952066

Thomas L. Magnanti, Prakash Mirchandani, Anantaram Balakrishnan

Publication date: 15 September 2003

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(01)00094-3

zbMATH Keywords

traveling salesmanSteiner network problemtelecommunication networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

A global optimization algorithm for reliable network design, The \(k\)-path tree matroid and its applications to survivable network design

Cites Work

• Minimum-weight two-connected spanning networks
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• Designing Hierarchical Survivable Networks
• Connectivity-splitting models for survivable network design
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item