A legkisebb k-vágás

A legkisebb k -vágás egy kombinatorikus optimalizálási probléma , amelyben meg kell találni egy olyan élhalmazt, amelynek eltávolítása k összefüggő komponensre osztja fel a gráfot . Ezeket az éleket k -vágásnak nevezzük . A feladat célja egy minimális súlyú k -vágás megtalálása. Egy ilyen partíciónak lehetnek alkalmazásai a VLSI fejlesztésében , az adatbányászatban , a végeselem-módszerben és az információcserében a párhuzamos számításokban .

Formális definíció

Adott egy irányítatlan G = ( V , E ) gráf adott w : E → N élsúlyokkal és egy k ∈ {2, 3, …, | V |} , V felosztása k diszjunkt halmazra F = { C 1 , C 2 , …, C k }, amelyekre

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

Rögzített k esetén a feladat megoldható O polinomidőben (| V | k 2 ) [1] . Egy probléma azonban NP-teljes , ha k a bemenet része [2] . A probléma akkor is NP-teljes, ha csúcsokat rögzítünk, és megpróbáljuk megtalálni a legkisebb -vágást, amely elválasztja ezeket a csúcsokat [3] $k$ $k$

Közelítések

Létezik néhány közelítő algoritmus 2 − 2/ k közelítéssel . Egy egyszerű mohó algoritmus , amely ilyen közelítő tényezőt ad, kiszámítja a legkisebb vágást minden egyes csatlakoztatott komponensben, és eltávolítja a legkönnyebbet. Az algoritmus összesen n − 1 számítást igényel a maximális áramlásra vonatkozóan . Egy másik, ugyanazt az együtthatót adó algoritmus a legkisebb vágások Gomory-Hu A Gomori-Hu fa felépítéséhez n − 1 maximális áramlási számítás szükséges, de az algoritmus összesen O ( kn ) maximális áramlási számítást igényel. Ennek ellenére könnyebb a második algoritmus közelítési együtthatójának elemzése [4] [5] .

Ha egy metrikus térben lévő gráfokra korlátozzuk magunkat, feltételezve, hogy a megfelelő teljes gráf kielégíti a háromszög egyenlőtlenséget , és ha megköveteljük, hogy az eredményül kapott partíciók előre meghatározott dimenziókkal rendelkezzenek, a problémát 3-szoros tényezővel közelítjük bármely rögzített k esetén [6] . Pontosabban, közelítő polinomiális idősémákat (PTAS) fedeztek fel az ilyen problémákra [7] .

Lásd még

Jegyzetek

↑ Goldschmidt, Hochbaum, 1988 .
↑ Garey, Johnson, 1979 .
↑ [1] Archiválva 2015. december 22-én a Wayback Machine -nél , ahol a cikkre hivatkoznak [2] Archivált 2012. augusztus 29-én a Wayback Machine -nél
↑ Saran, Vazirani, 1991 .
↑ Vazirani, 2003 , p. 40-44.
↑ Guttmann-Beck és Hassin 1999 , p. 198-207.
↑ Fernandez de la Vega, Karpinski, Kenyon, 2004 .

Irodalom

O. Goldschmidt, D. S. Hochbaum. Proc. 29. Ann. IEEE Symp. a számítástechnika alapjairól. Sci .. - IEEE Computer Society, 1988. - S. 444-451.
MR Garey, D.S. Johnson. Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W.H. Freeman, 1979. - ISBN 0-7167-1044-7 .
H. Saran, V. Vazirani. A k -vágás megtalálása az optimális kétszeresén belül // Proc . 32. Ann. IEEE Symp. a számítástechnika alapjairól. Sci . - IEEE Computer Society, 1991. - S. 743-751. Archiválva : 2015. október 15. a Wayback Machine -nél
Vijay V. Vazirani. Közelítő algoritmusok. - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
N. Guttmann-Beck, R. Hassin. Közelítő algoritmusok minimális k -vágáshoz // Algorithmica . - 1999. - S. 198-207.
Francesc Comellas, Emily Sapena. Többágens algoritmus gráfparticionáláshoz. Előadásjegyzetek a számítástechnikában. sci. // Algorithmica. - 2006. - T. 3907 . - S. 279-285 . — ISSN 0302-9743 . - doi : 10.1007/s004530010013 . Az eredetiből archiválva: 2009. december 12.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger. Minimum k-cut // Az NP optimalizálási problémák gyűjteménye . – 2000.
W. Fernandez de la Vega, M. Karpinski, C. Mathieu. Közelítő sémák a metrikus felezéshez és a particionáláshoz // Proceedings of the tizenötödik éves ACM-SIAM szimpózium a diszkrét algoritmusokról . - 2004. - S. 506-515,.