Approximability of capacitated network design
DOI10.1007/978-3-642-20807-2_7zbMATH Open1339.90321OpenAlexW2568450825MaRDI QIDQ3009752FDOQ3009752
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
Recommendations
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)
Cites Work
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Title not available (Why is that?)
- Proof verification and the hardness of approximation problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem
- A Parallel Repetition Theorem
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- Approximation algorithms for node-weighted buy-at-bulk network design
- Title not available (Why is that?)
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- Minimum-cost network design with (dis)economies of scale
- Approximability of capacitated network design
- On the approximability of some network design problems
- Title not available (Why is that?)
Cited In (21)
- Optimal design of capacitated production networks
- On fixed cost \(k\)-flow problems
- Title not available (Why is that?)
- 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
- Approximation algorithms for prize-collecting capacitated 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)
