Approximability of capacitated network design

DOI10.1007/978-3-642-20807-2_7MaRDI QIDQ3009752zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula

Publication date 24 June 2011

Published in Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL https://repository.upenn.edu/cgi/viewcontent.cgi?article=1701&context=cis_papers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Recommendations

• Approximability of capacitated network design
• Inapproximability of Survivable Networks
• Inapproximability of survivable networks
• scientific article; zbMATH DE number 1947057
• On the approximability of some network design problems

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 1559550 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 6472640 (Why is no real title available?)
• A Parallel Repetition Theorem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Approximability of capacitated network design
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximation algorithms for node-weighted buy-at-bulk network design
• Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Minimum-cost network design with (dis)economies of scale
• On the approximability of some network design problems
• Proof verification and the hardness of approximation problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(21)

• Approximation algorithms for prize-collecting capacitated network design problems
• On fixed cost k-flow problems
• Optimal design of capacitated production networks
• scientific article; zbMATH DE number 1947057 (Why is no real title available?)
• The convex hull of two core capacitated network design problems
• Improved approximation for fractionally subadditive network design
• Hallucination helps: energy efficient virtual circuit routing
• Capacitated network design on undirected graphs
• Approximability of capacitated network design
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• Complexity and Approximation of the Continuous Network Design Problem
• Algorithms – ESA 2005
• On the approximability of some network design problems
• A polyhedral study of the capacity formulation of the multilayer network design problem
• Survivable network design: the capacitated minimum spanning network problem
• A characterization of the uncapacitated network design polytope
• The minimum vulnerability problem
• Approximation algorithms for a capacitated network design problem
• On the approximability of some network design problems
• Feasibility in capacitated networks: The effect of individual arcs and nodes
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands

This page was built for publication: Approximability of capacitated network design

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