Approximability of Capacitated Network Design
From MaRDI portal
Publication:3009752
DOI10.1007/978-3-642-20807-2_7zbMath1339.90321OpenAlexW2568450825MaRDI QIDQ3009752
Deeparnab Chakrabarty, Nitish Korula, Chandra Chekuri, Sanjeev Khanna
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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)
Related Items (5)
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ The minimum vulnerability problem ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ On fixed cost \(k\)-flow problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A factor 2 approximation algorithm for the generalized Steiner network problem
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Approximability of capacitated network design
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem
- Proof verification and the hardness of approximation problems
- Minimum-Cost Network Design with (Dis)economies of Scale
- A Parallel Repetition Theorem
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
This page was built for publication: Approximability of Capacitated Network Design
