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)

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

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)