Mindste k-snit

Det mindste k -snit er et kombinatorisk optimeringsproblem , hvor det er nødvendigt at finde et sæt kanter, hvis fjernelse opdeler grafen i k forbundne komponenter. Disse kanter kaldes k -cut . Målet med problemet er at finde et k -snit med en minimumsvægt. En sådan partition kan have applikationer til udvikling af VLSI , data mining , finite element-metode og informationsudveksling i parallel computing .

Formel definition

Givet en urettet graf G  = ( V ,  E ) med givne kantvægte w :  E  →  N og et heltal k  ∈ {2, 3, …, | V |}, en opdeling af V i k disjunkte sæt F  = { C 1 ,  C 2 , …,  C k }, for hvilke

For en fast k kan problemet løses i polynomisk tid O (| V | k 2 ) [1] . Et problem er dog NP-komplet, hvis k er en del af inputtet [2] . Problemet er også NP-komplet, hvis vi fikser hjørner og forsøger at finde det mindste -snit, der adskiller disse knudepunkter [3]

Approksimationer

Der er nogle tilnærmelsesalgoritmer med tilnærmelse 2 − 2/ k . En simpel grådig algoritme , der giver en sådan tilnærmelsesfaktor, beregner det mindste snit i hver tilsluttet komponent og fjerner den letteste. Algoritmen kræver i alt n  −1 beregninger af det maksimale flow . En anden algoritme, der giver den samme koefficient, bruger Gomory-Hu trærepræsentationen af ​​de mindste snit. Opbygning af et Gomori-Hu træ kræver n  − 1 maksimale flowberegninger, men algoritmen kræver i alt O ( kn ) maksimale flowberegninger. Alligevel er det lettere at analysere tilnærmelseskoefficienten for den anden algoritme [4] [5] .

Hvis vi begrænser os til grafer i et metrisk rum, idet vi antager, at den tilsvarende komplette graf opfylder trekantsuligheden , og hvis vi kræver, at de resulterende partitioner har forudbestemte dimensioner, tilnærmes problemet med en faktor 3 for enhver fast k [6] . Mere præcist er tilnærmede polynomielle tidsskemaer (PTAS) for sådanne problemer blevet opdaget [7] .

Se også

• Maksimal grafsnit
• mindste snit

Noter

1. ↑ Goldschmidt, Hochbaum, 1988 .
2. ↑ Garey, Johnson, 1979 .
3. ↑ [1] Arkiveret 22. december 2015 på Wayback Machine , hvor artiklen er citeret [2] Arkiveret 29. august 2012 på Wayback Machine
4. ↑ Saran, Vazirani, 1991 .
5. ↑ Vazirani, 2003 , s. 40-44.
6. ↑ Guttmann-Beck og Hassin 1999 , s. 198-207.
7. ↑ Fernandez de la Vega, Karpinski, Kenyon, 2004 .

Litteratur

• O. Goldschmidt, D. S. Hochbaum. Proc. 29. Ann. IEEE Symp. om Fundamenter af Comput. Sci .. - IEEE Computer Society, 1988. - S. 444-451.
• MR Garey, D.S. Johnson. Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W.H. Freeman, 1979. - ISBN 0-7167-1044-7 .
• H. Saran, V. Vazirani. Finde k -snit inden for det dobbelte af det optimale // Proc. 32. Ann. IEEE Symp. om Fundamenter af Comput. Sci . - IEEE Computer Society, 1991. - S. 743-751. Arkiveret 15. oktober 2015 på Wayback Machine
• Vijay V. Vazirani. Approksimationsalgoritmer. - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
• N. Guttmann-Beck, R. Hassin. Approksimationsalgoritmer for minimum k -cut // Algorithmica . - 1999. - S. 198-207.
• Francesc Comellas, Emily Sapena. En multiagent-algoritme til grafopdeling. Forelæsningsnoter i Comput. sci.  // Algoritmik. - 2006. - T. 3907 . - S. 279-285 . — ISSN 0302-9743 . - doi : 10.1007/s004530010013 . Arkiveret fra originalen den 12. december 2009.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger. Minimum k-cut // Et kompendium over NP-optimeringsproblemer . - 2000.
• W. Fernandez de la Vega, M. Karpinski, C. Mathieu. Tilnærmelsesskemaer for metrisk opdeling og opdeling // Proceedings of the femtende årlige ACM-SIAM symposium on Discrete Algorithms . - 2004. - S. 506-515,.