An improved approximation algorithm for requirement cut

DOI10.1016/j.orl.2010.02.009zbMath1194.05146OpenAlexW1992849490MaRDI QIDQ991474

Viswanath Nagarajan, R. Ravi, Anupam Gupta

Publication date: 7 September 2010

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2010.02.009

zbMATH Keywords

graph partitioningapproximation algorithmsrequirement cut problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Terminal embeddings ⋮ Network design with a discrete set of traffic matrices ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Approximating Requirement Cut via a Configuration LP ⋮ Improved approximation for fractionally subadditive network design ⋮ Unnamed Item ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points

Cites Work

• Approximation algorithms for requirement cut on graphs
• The multi-multiway cut problem
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Approximation Algorithms for Steiner and Directed Multicuts
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• The Steiner k-Cut Problem
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: An improved approximation algorithm for requirement cut