Minsta k-snitt

Det minsta k -snittet är ett kombinatoriskt optimeringsproblem där det krävs att hitta en uppsättning kanter vars borttagning delar upp grafen i k anslutna komponenter. Dessa kanter kallas k -cut . Målet med problemet är att hitta ett k -snitt med en minimal vikt. En sådan partition kan ha tillämpningar inom utveckling av VLSI , datautvinning , finita elementmetod och informationsutbyte vid parallell beräkning .

Formell definition

Givet en oriktad graf G = ( V , E ) med givna kantvikter w : E → N och ett heltal k ∈ {2, 3, …, | V |}, en uppdelning av V i k disjunkta uppsättningar F = { C 1 , C 2 , …, C k }, för vilka

\sum _{i=1}^{k-1}\sum _{j=i+1}^{k}\summa _{\begin{smallmatrix}v_{1}\in C_{i} \\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})

För ett fast k är problemet lösbart i polynomtid O (| V | k 2 ) [1] . Ett problem är dock NP-komplett om k är en del av ingången [2] . Problemet är också NP-komplett om vi fixar hörn och försöker hitta det minsta -snitt som skiljer dessa hörn åt [3] $k$ $k$

Approximationer

Det finns några approximationsalgoritmer med approximation 2 − 2/ k . En enkel girig algoritm som ger en sådan approximationsfaktor beräknar det minsta snittet i varje ansluten komponent och tar bort den lättaste. Algoritmen kräver totalt n −1 beräkningar av maximalt flöde . En annan algoritm som ger samma koefficient använder Gomory-Hu trädrepresentationen av de minsta snitten. Att bygga ett Gomori-Hu-träd kräver n − 1 maximala flödesberäkningar, men algoritmen kräver totalt O ( kn ) maximala flödesberäkningar. Ändå är det lättare att analysera approximationskoefficienten för den andra algoritmen [4] [5] .

Om vi begränsar oss till grafer i ett metriskt utrymme, förutsatt att den motsvarande kompletta grafen uppfyller triangelolikheten , och om vi kräver att de resulterande partitionerna har förutbestämda dimensioner, approximeras problemet med en faktor 3 för varje fast k [6] . Mer exakt har ungefärliga polynomiska tidsscheman (PTAS) för sådana problem upptäckts [7] .

Se även

Anteckningar

↑ Goldschmidt, Hochbaum, 1988 .
↑ Garey, Johnson, 1979 .
↑ [1] Arkiverad 22 december 2015 på Wayback Machine , där artikeln citeras [2] Arkiverad 29 augusti 2012 på Wayback Machine
↑ Saran, Vazirani, 1991 .
↑ Vazirani, 2003 , sid. 40-44.
↑ Guttmann-Beck och Hassin 1999 , sid. 198-207.
↑ Fernandez de la Vega, Karpinski, Kenyon, 2004 .

Litteratur

O. Goldschmidt, D.S. Hochbaum. Proc. 29:e Ann. IEEE Symp. på Foundations of Comput. Sci .. - IEEE Computer Society, 1988. - S. 444-451.
MR Garey, D.S. Johnson. Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . - W.H. Freeman, 1979. - ISBN 0-7167-1044-7 .
H. Saran, V. Vazirani. Hitta k -snitt inom dubbelt så optimalt // Proc. 32:a Ann. IEEE Symp. på Foundations of Comput. Sci . - IEEE Computer Society, 1991. - S. 743-751. Arkiverad 15 oktober 2015 på Wayback Machine
Vijay V. Vazirani. Approximationsalgoritmer. - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
N. Guttmann-Beck, R. Hassin. Approximationsalgoritmer för minimum k -cut // Algorithmica . - 1999. - S. 198-207.
Francesc Comellas, Emily Sapena. En multiagent-algoritm för grafpartitionering. Föreläsningsanteckningar i Comput. sci. // Algoritmik. - 2006. - T. 3907 . - S. 279-285 . — ISSN 0302-9743 . - doi : 10.1007/s004530010013 . Arkiverad från originalet den 12 december 2009.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger. Minsta k-cut // Ett kompendium över NP-optimeringsproblem . — 2000.
W. Fernandez de la Vega, M. Karpinski, C. Mathieu. Approximationsscheman för metrisk uppdelning och uppdelning // Proceedings of the femtonde årliga ACM-SIAM symposiet on Discrete Algorithms . - 2004. - S. 506-515,.