Pienin k-leikkaus

Pienin k - leikkaus on kombinatorinen optimointitehtävä , jossa on löydettävä joukko reunoja, joiden poistaminen jakaa graafin k :ksi yhdistetyksi komponentiksi. Näitä reunoja kutsutaan k -leikkauksiksi . Tehtävän tavoitteena on löytää k - leikkaus minimipainolla. Tällaisella osiolla voi olla sovelluksia VLSI :n , tiedon louhinnan , elementtimenetelmän ja tiedonvaihdon kehittämiseen rinnakkaislaskennassa .

Muodollinen määritelmä

Annettu suuntaamaton graafi G = ( V , E ) annetuilla reunapainoilla w : E → N ja kokonaisluvulla k ∈ {2, 3, …, | V |}, V : n osio k disjunktijoukkoon F = { C 1 , C 2 , …, C k }, joille

\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\})

Kiinteällä k :lla ongelma on ratkaistavissa polynomiajassa O (| V | k 2 ) [1] . Ongelma on kuitenkin NP-täydellinen , jos k on osa syötettä [2] . Ongelma on myös NP-täydellinen, jos korjaamme pisteet ja yritämme löytää pienin -leikkaus, joka erottaa nämä kärjet [3] $k$ $k$

Arviot

On olemassa joitakin approksimaatioalgoritmeja, joiden approksimaatio on 2 − 2/ k . Yksinkertainen ahne algoritmi , joka antaa tällaisen approksimaatiokertoimen, laskee kunkin yhdistetyn komponentin pienimmän leikkauksen ja poistaa kevyimmän. Algoritmi vaatii yhteensä n − 1 maksimivirtauksen laskentaa . Toinen algoritmi, joka antaa saman kertoimen, käyttää pienimpien leikkausten Gomory-Hu -puuesitystä . Gomori-Hu-puun rakentaminen vaatii n − 1 maksimivirtauslaskentaa, mutta algoritmi vaatii yhteensä O ( kn ) maksimivirtauslaskentaa. Toisen algoritmin approksimaatiokerrointa on kuitenkin helpompi analysoida [4] [5] .

Jos rajoitamme metrisen avaruuden kuvaajiin olettaen, että vastaava täydellinen graafi täyttää kolmio-epäyhtälön , ja jos edellytämme, että tuloksena olevilla osioilla on ennalta määrätyt mitat, ongelma on likimääräinen kertoimella 3 mille tahansa kiinteälle k :lle [6] . Tarkemmin sanottuna tällaisille ongelmille on löydetty likimääräisiä polynomiaikakaavioita (PTAS) [7] .

Katso myös

Muistiinpanot

↑ Goldschmidt, Hochbaum, 1988 .
↑ Garey, Johnson, 1979 .
↑ [1] Arkistoitu 22. joulukuuta 2015 Wayback Machineen , jossa artikkeli on lainattu [2] Arkistoitu 29. elokuuta 2012 Wayback Machinessa
↑ Saran, Vazirani, 1991 .
↑ Vazirani, 2003 , s. 40-44.
↑ Guttmann-Beck ja Hassin 1999 , s. 198-207.
↑ Fernandez de la Vega, Karpinski, Kenyon, 2004 .

Kirjallisuus

O. Goldschmidt, D. S. Hochbaum. Proc. 29. Ann. IEEE Symp. Perusteet of Comput. Sci.. - IEEE Computer Society, 1988. - S. 444-451.
MR Garey, D.S. Johnson. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W.H. Freeman, 1979. - ISBN 0-7167-1044-7 .
H. Saran, V. Vazirani. K -leikkausten löytäminen kaksinkertaisen optimaalisen arvon sisällä // Proc. 32. Ann. IEEE Symp. Perusteet of Comput. Sci . - IEEE Computer Society, 1991. - S. 743-751. Arkistoitu 15. lokakuuta 2015 Wayback Machinessa
Vijay V. Vazirani. Approksimaatioalgoritmit. - Berliini: Springer, 2003. - ISBN 3-540-65367-8 .
N. Guttmann-Beck, R. Hassin. Approksimaatioalgoritmit minimik - leikkaukselle // Algorithmica . - 1999. - S. 198-207.
Francesc Comellas, Emily Sapena. Moniagenttialgoritmi graafin osiointiin. Luentomuistiinpanot tietokoneessa. sci. // Algorithmica. - 2006. - T. 3907 . - S. 279-285 . — ISSN 0302-9743 . - doi : 10.1007/s004530010013 . Arkistoitu alkuperäisestä 12. joulukuuta 2009.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger. Minimi k-leikkaus // NP-optimointiongelmien kokoelma . – 2000.
W. Fernandez de la Vega, M. Karpinski, C. Mathieu. Approksimaatiokaaviot metristä puolittamista ja osiointia varten // Proceedings of the viidentoista vuotuinen ACM-SIAM symposium on Discrete Algorithms . - 2004. - S. 506-515,.