FINDING K-CUTS WITHIN TWICE THE OPTIMAL

Authors
SARAN H VAZIRANI VV
Citation
H. Saran et Vv. Vazirani, FINDING K-CUTS WITHIN TWICE THE OPTIMAL, SIAM journal on computing, 24(1), 1995, pp. 101-108
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
24
Issue
1
Year of publication
1995
Pages
101 - 108
Database
ISI
SICI code
0097-5397(1995)24:1<101:FKWTTO>2.0.ZU;2-U
Abstract
Two simple approximation algorithms for the minimum k-cut problem are presented. Each algorithm finds a k cut having weight within a factor of (2-2/k) of the optimal. One algorithm is particularly efficient-it requires a total of only n-1 maximum flow computations for finding a s et of near-optimal k cuts, one for each value of k between 2 and n.