An improved approximation algorithm for requirement cut

DOI10.1016/J.ORL.2010.02.009MaRDI QIDQ991474zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Viswanath Nagarajan, R. Ravi

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

approximation algorithmsgraph partitioningrequirement cut problem

Mathematics Subject Classification ID

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation algorithms for requirement cut on graphs
• On cutting a few vertices from a graph
• An improved approximation algorithm of MULTIWAY CUT.
• scientific article; zbMATH DE number 1775387

Cites work

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

Cited in

(10)

• Single-sink fractionally subadditive network design
• Improved approximation for fractionally subadditive network design
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Approximation algorithms for requirement cut on graphs
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Terminal embeddings
• Network design with a discrete set of traffic matrices
• Approximating Requirement Cut via a Configuration LP
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991474)