Approximability of capacitated network design
From MaRDI portal
Abstract: In the {em capacitated} survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood; even in very restricted settings no known algorithm achieves a approximation, where is the number of edges in the graph. In this paper, we obtain several new results and insights into the approximability of Cap-SNDP.
Recommendations
Cites work
- scientific article; zbMATH DE number 1003253 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 1559550 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- scientific article; zbMATH DE number 6472640 (Why is no real title available?)
- A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
- Analysis of a flow problem with fixed charges
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- Approximation algorithms for nonuniform buy-at-bulk network design
- Capacitated network design on undirected graphs
- Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- On capacitated network design cut-set polyhedra
- On network design problems: fixed cost flows and the covering steiner problem
- On the approximability of some network design problems
- Polylogarithmic inapproximability
- Random sampling in cut, flow, and network design problems
Cited in
(19)- The convex hull of two core capacitated network design problems
- Algorithms – ESA 2005
- Robust \(k\)-center with two types of radii
- Robust \(k\)-center with two types of radii
- Complexity and Approximation of the Continuous Network Design Problem
- Fast and Deterministic Approximations for k-Cut.
- Capacitated network design on undirected graphs
- Flexible graph connectivity
- Feasibility in capacitated networks: The effect of individual arcs and nodes
- Cluster before you hallucinate: node-capacitated network design and energy efficient routing
- A polyhedral study of the capacity formulation of the multilayer network design problem
- Approximation algorithms for a capacitated network design problem
- Approximation algorithm for prize-collecting vertex cover with fairness constraints
- Approximability of capacitated network design
- A characterization of the uncapacitated network design polytope
- Optimal design of capacitated production networks
- Fast and deterministic approximations for \(k\)-cut
- Improved approximation for fractionally subadditive network design
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
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 Q2354026)
