Hardness of approximation for vertex-connectivity network-design problems

DOI10.1007/3-540-45753-4_17MaRDI QIDQ4411287zbMATH OpenFDO

Authors Robert Krauthgamer, James R. Lee, Guy Kortsarz

Publication date 7 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2462/24620185.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Inapproximability of Survivable Networks
• Inapproximability of survivable networks
• An O(k^3 n)-approximation algorithm for vertex-connectivity survivable network design
• Approximability of capacitated network design

Cited in

(15)

• Inapproximability of survivable networks
• Approximability of capacitated network design
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• An O(k^3 n)-approximation algorithm for vertex-connectivity survivable network design
• Approximability of capacitated network design
• Single-sink network design with vertex connectivity requirements
• Inapproximability of Survivable Networks
• A 2-approximation for minimum cost {0,1,2} vertex connectivity
• Parameterized algorithms for survivable network design with uniform demands
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• scientific article; zbMATH DE number 6423757 (Why is no real title available?)
• Parameters of two-prover-one-round game and the hardness of connectivity problems
• Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
• The parameterized complexity of the survivable network design problem
• The parameterized complexity of the survivable network design problem

This page was built for publication: Hardness of approximation for vertex-connectivity network-design problems

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