Finding k-cuts within twice the optimal
Published 9 December 2002
Huzur Saran, Vijay V. Vazirani
Citations61
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two simple approximation algorithms are presented for the minimum k-cut problem, requiring a total of only n-1 maximum flow computations for finding a set of near-optimal k-cuts.
Abstract
Two simple approximation algorithms are presented for the minimum k-cut problem. Each algorithm finds a k-cut having weight within a factor of (2-2/k) of the optimal. One of the algorithms is particularly efficient, requiring a total of only n-1 maximum flow computations for finding a set of near-optimal k-cuts, one for each value of k between 2 and n.>
Keywords
Computer Science
Bell System Technical JournalAn Efficient Heuristic Procedure for Partitioning Graphs
5,218 Citations1970Brian W. Kernighan, Shang Min Lin
A heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems is presented.
Journal of the ACMA new approach to the maximum-flow problem
1,877 Citations1988Andrew V. Goldberg, Robert E. Tarjan
An alternative method based on the preflow concept of Karzanov, which runs as fast as any other known method on dense graphs, achieving an O(n) time bound on an n-vertex graph and faster on graphs of moderate density.
Journal of the Society for Industrial and Applied MathematicsMulti-Terminal Network Flows
940 Citations1961Ralph E. Gomory, T. C. Hu
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
399 Citations1988T. Leighton, S. Rao
The main result is an algorithm for performing the task provided that the capacity of each cut exceeds the demand across the cut by a Theta (log n) factor.
Approximating clique is almost NP-complete
397 Citations2002Uriel Feige, S. Goldwasser +3 more
The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered and it is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P.
A new approach to the maximum flow problem
326 Citations1986Andrew V. Goldberg, Robert E. Tarjan
By incorporating the dynamic tree data structure of Sleator and Tarjan, a version of the algorithm running in O(nm log(n'/m)) time on an n-vertex, m-edge graph is obtained, as fast as any known method for any graph density and faster on graphs of moderate density.
Journal of the ACMOptimal attack and reinforcement of a network
257 Citations1985William H. Cunningham
Efficient algorithms for the optimal attack problem, the problem of computing the strength, and the problems of finding a minimum cost “reinforcement” to achieve a desired strength are given.
Fast approximation algorithms for multicommodity flow problems
205 Citations1991Tom Leighton, Clifford Stein +4 more
It is proved that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-comodity minimum-cost flow problems, and the first polynomial-time combinatorial algorithms for approximately solving the multicommodation flow problem are described.
Polynomial algorithm for the k-cut problem
192 Citations1988Olivier Goldschmidt, Dorit S. Hochbaum
A polynomial algorithm for the case of a fixed k, to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum.
Information Processing LettersGenerating pseudo-random permutations and maximum flow algorithms
43 Citations1990Noga Alon
A simple construction of a family of permutations with a certain pseudo-random property can be used to derandomize a recent randomized maximum-flow algorithm of Cheriyan and Hagerup for all relatively dense networks.
SIAM Journal on Algebraic and Discrete MethodsAn $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
30 Citations1985Dorit S. Hochbaum, David B. Shmoys
Journal of AlgorithmsAn improved algorithm for the planar 3-cut problem
21 Citations1991Xin He
This paper presents an O ( n log n ) algorithm for finding a minimum 3-cut in planar graphs and improves the best previously known algorithm for the problem by an O( n logn) factor.
A randomized maximum-flow algorithm
19 Citations1989Joseph Cheriyan, Torben Hagerup
The authors present a randomized maximum-flow algorithm, called the PLED (prudent linking excess diminishing) algorithm, whose expected running time is O(nm+n/sup 2/(log n)/sup 3/); this is O (nm) for all except relatively sparse networks.