On the approximability of some network design problems

MaRDI QIDQ2921762zbMATH OpenFDO

Authors Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor, Amitabh Sinha

Publication date 13 October 2014

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the approximability of some network design problems
• Approximability of capacitated network design
• Approximation algorithms for a capacitated network design problem
• On the approximability of robust network design
• Inapproximability of survivable networks

Cited in

(19)

• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Inapproximability and a polynomially solvable special case of a network improvement problem.
• The non-approximability of bicriteria network design problems
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• On the approximability of robust network design
• Approximability of capacitated network design
• Network design with a discrete set of traffic matrices
• A 2-approximation algorithm for the network substitution problem
• Complexity and Approximation of the Continuous Network Design Problem
• Approximability of capacitated network design
• On capacitated set cover problems
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• Online Priority Steiner Tree Problems
• Hardness of robust network design
• scientific article; zbMATH DE number 4068646 (Why is no real title available?)
• AN EFFICIENT COMPLETE ENUMERATION METHOD FOR NETWORK DESIGN PROBLEMS AND ITS APPLICATIONS
• On the approximability of some network design problems
• The Priority k-Median Problem
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph

This page was built for publication: On the approximability of some network design problems

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