An improved approximation algorithm for requirement cut
type: Item
instance of: scholarly article
title: An improved approximation algorithm for requirement cut
zbMATH Open document ID: 1194.05146
author: Anupam Gupta
author: Viswanath Nagarajan
author: R. Ravi
published in: Operations Research Letters
publication date: 2010-09-07T00:00:00Z
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5780112
zbMATH Keywords: graph partitioning
zbMATH Keywords: approximation algorithms
zbMATH Keywords: requirement cut problem
MaRDI profile type: Publication
full work available at URL: j.orl.2010.02.009
OpenAlex ID: W1992849490
cites work: The multi-multiway cut problem
cites work: The Steiner k-Cut Problem
cites work: The Complexity of Multiterminal Cuts
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Approximation Algorithms for Steiner and Directed Multicuts
cites work: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
cites work: Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
cites work: Approximation algorithms for requirement cut on graphs
cites work: Finding k Cuts within Twice the Optimal
DOI: 10.1016/J.ORL.2010.02.009
description: scientific article; zbMATH DE number 5780112