Approximability of Capacitated Network Design

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

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)

Related Items

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