Approximability of capacitated network design
From MaRDI portal
Publication:2354026
DOI10.1007/s00453-013-9862-4zbMath1327.90023arXiv1009.5734MaRDI QIDQ2354026
Sanjeev Khanna, Chandra Chekuri, Deeparnab Chakrabarty, Nitish Korula
Publication date: 10 July 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.5734
90C35: Programming involving graphs or networks
90B10: Deterministic network models in operations research
68W25: Approximation algorithms
Related Items
Unnamed Item, Robust \(k\)-center with two types of radii, Robust \(k\)-center with two types of radii, Fast and Deterministic Approximations for k-Cut., Approximation algorithms for flexible graph connectivity, Flexible graph connectivity, Approximability of Capacitated Network Design
Cites Work
- Unnamed Item
- 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
- On capacitated network design cut-set polyhedra
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Random sampling in cut, flow, and network design problems
- Capacitated Network Design on Undirected Graphs
- Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem
- On network design problems: fixed cost flows and the covering steiner problem
- Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
- Polylogarithmic inapproximability
- Analysis of a flow problem with fixed charges
- A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
