Welding defect

2014-01-28T19:32:54Z

204.54.36.245: spelling correction

In mathematics, the '''minimum ''k''-cut''', is a [[combinatorial optimization]] problem that requires finding a set of edges whose removal would partition the graph to ''k'' connected components. These edges are referred to as '''''k''-cut'''. The goal is to find the minimum-weight ''k''-cut. This partitioning can have applications in [[VLSI]] design, [[data-mining]], [[finite elements]] and communication in [[parallel computing]].

==Formal definition==
Given an undirected graph ''G'' = (''V'', ''E'') with an assignment of weights to the edges ''w'': ''E'' → ''N'' and an integer ''k'' ∈ {2, 3, …, |''V''|}, partition ''V'' into ''k'' disjoint sets ''F'' = {''C''1, ''C''2, …, ''C''''k''} while minimizing

: <math>\sum_{i=1}^{k-1}\sum_{j=i+1}^k\sum_{\begin{smallmatrix} v_1 \in C_i \\ v_2 \in C_j \end{smallmatrix}} w ( \left \{ v_1, v_2 \right \} )</math>

For a fixed ''k'', the problem is [[polynomial time]] solvable in ''O''(|''V''|''k''2).<ref>{{harvnb|Goldschmidt|Hochbaum|1988}}.</ref> However, the problem is [[NP-complete]] if ''k'' is part of the input.<ref>{{harvnb|Garey|Johnson|1979}}</ref> It is also NP-complete if we specify <math>k</math> vertices and ask for the minimum <math>k</math>-cut which separates these vertices among each of the sets.<ref>[http://www.jstor.org/stable/3690374?seq=13], which cites [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6534]</ref>

==Approximations==
Several [[approximation algorithms]] exist with an approximation of 2 − 2/''k''. A simple [[greedy algorithm]] that achieves this approximation factor computes a [[minimum cut]] in each connected components and removes the lightest one. This algorithm requires a total of ''n'' − 1 [[max flow]] computations. Another algorithm achieving the same guarantee uses the [[Gomory–Hu tree]] representation of minimum cuts. Constructing the Gomory–Hu tree requires ''n'' − 1 max flow computations, but the algorithm requires an overall ''O''(''kn'') max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm.<ref>{{harvnb|Saran|Vazirani|1991}}.</ref><ref>{{harvnb|Vazirani|2003|pp=40–44}}.</ref>

If we restrict the graph to a metric space, meaning a [[complete graph]] that satisfies the [[triangle inequality]], and enforce that the output partitions are each of pre-specified sizes, the problem is approximable to within a factor of  3 for any fixed ''k''.<ref>{{harvnb|Guttmann-Beck|Hassin|1999|pp=198–207}}.</ref>

==See also==
* [[Maximum cut]]
* [[Minimum cut]]

==Notes==
<references />

==References==
* {{citation
| first1=O.
| last1=Goldschmidt
| first2=D. S.
| last2=Hochbaum
| title=Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci.
| publisher=IEEE Computer Society
| year=1988
| pages=444–451 }}
* {{citation
| first1=M. R.
| last1=Garey
| first2=D. S.
| last2=Johnson
| title=Computers and Intractability: A Guide to the Theory of NP-Completeness
| publisher = W.H. Freeman
| year=1979
| isbn = 0-7167-1044-7 }}
* {{citation
| first1=H.
| last1=Saran
| first2=V.
| last2=Vazirani
| contribution=Finding ''k''-cuts within twice the optimal
| contribution-url=http://www.cc.gatech.edu/~vazirani/k-cut.ps
| title=Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci
| publisher=IEEE Computer Society
| year=1991
| pages=743–751 }}
* {{citation
| last = Vazirani
| first = Vijay V.
| authorlink = Vijay Vazirani
| title = Approximation Algorithms
| publisher = Springer
| year = 2003
| location = Berlin
| isbn = 3-540-65367-8 }}
* {{citation
| last1 = Guttmann-Beck
| first1 = N.
| last2 = Hassin
| first2 = R.
| contribution = Approximation algorithms for minimum ''k''-cut
| contribution-url = http://www.math.tau.ac.il/~hassin/k_cut_00.pdf
| title = Algorithmica
| year = 1999
| pages = 198–207 }}
* {{citation
| last1 = Comellas
| first1 = Francesc
| last2 = Sapena
| first2 = Emili
| title = A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci.
| year = 2006
| volume = 3907
| pages = 279–285
| issn = 0302-9743
| doi= 10.1007/s004530010013
| journal = Algorithmica
| issue = 2
| url=http://www-ma4.upc.es/~comellas/evocomnet06/CoSa06-EvoCOMNET06.html}}
* {{citation
| last1=Crescenzi | first1=Pierluigi
| last2=Kann | first2=Viggo
| last3=Halldórsson | first3=Magnús
| last4=Karpinski | first4=Marek | authorlink4=Marek Karpinski
| last5=Woeginger | first5=Gerhard
| title=A Compendium of NP Optimization Problems
| contribution=Minimum k-cut
| url=http://www.csc.kth.se/~viggo/wwwcompendium/node90.html
| year=2000 }}

[[Category:NP-complete problems]]
[[Category:Combinatorial optimization]]
[[Category:Computational problems in graph theory]]
[[Category:Approximation algorithms]]

formulasearchengine - User contributions [en]

Welding defect