Approximability of Capacitated Network Design

DOI10.1007/978-3-642-20807-2_7zbMath1339.90321MaRDI 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

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90B10: Deterministic network models in operations research

68W25: Approximation algorithms

Related Items

Hallucination Helps: Energy Efficient Virtual Circuit Routing, On fixed cost \(k\)-flow problems, The minimum vulnerability problem, A tight algorithm for strongly connected Steiner subgraph on two terminals with demands, A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item