Cea mai mică tăietură k

Cea mai mică k -cut este o problemă de optimizare combinatorie în care este necesar să se găsească un set de muchii a căror îndepărtare împarte graficul în k componente conectate. Aceste muchii se numesc k -cut . Scopul problemei este de a găsi o tăietură k cu o greutate minimă. O astfel de partiție poate avea aplicații în dezvoltarea VLSI , data mining , metoda elementelor finite și schimbul de informații în calcul paralel .

Definiție formală

Dat un grafic nedirecționat G = ( V , E ) cu ponderi date ale muchiilor w : E → N și un întreg k ∈ {2, 3, …, | V |}, o partiție a lui V în k mulțimi disjunse F = { C 1 , C 2 , …, C k }, pentru care

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

Pentru un k fix , problema este rezolvabilă în timpul polinomial O (| V | k 2 ) [1] . Totuși, o problemă este NP-completă dacă k este parte din intrarea [2] . Problema este, de asemenea, NP-completă dacă fixăm vârfuri și încercăm să găsim cea mai mică tăietură care separă acele vârfuri [3] $k$ $k$

Aproximații

Există câțiva algoritmi de aproximare cu aproximarea 2 − 2/ k . Un algoritm simplu lacom care oferă un astfel de factor de aproximare calculează cea mai mică tăietură din fiecare componentă conectată și o elimină pe cea mai ușoară. Algoritmul necesită un total de n − 1 calcule ale debitului maxim . Un alt algoritm care oferă același coeficient folosește reprezentarea arborelui Gomory-Hu a celor mai mici tăieturi. Construirea unui arbore Gomori-Hu necesită n - 1 calcule de debit maxim, dar algoritmul necesită un total de calcule de debit maxim O ( kn ). Totuși, este mai ușor de analizat coeficientul de aproximare al celui de-al doilea algoritm [4] [5] .

Dacă ne limităm la grafice dintr-un spațiu metric, presupunând că graficul complet corespunzător satisface inegalitatea triunghiului și dacă solicităm ca partițiile rezultate să aibă dimensiuni predeterminate, problema este aproximată cu un factor de 3 pentru orice k fix [6] . Mai precis, au fost descoperite scheme de timp polinomiale aproximative (PTAS) pentru astfel de probleme [7] .

Vezi și

Note

↑ Goldschmidt, Hochbaum, 1988 .
↑ Garey, Johnson, 1979 .
↑ [1] Arhivat la 22 decembrie 2015 la Wayback Machine , unde este citat articolul [2] Arhivat la 29 august 2012 la Wayback Machine
↑ Saran, Vazirani, 1991 .
↑ Vazirani, 2003 , p. 40-44.
↑ Guttmann-Beck și Hassin 1999 , p. 198-207.
↑ Fernandez de la Vega, Karpinski, Kenyon, 2004 .

Literatură

O. Goldschmidt, D. S. Hochbaum. Proc. a 29-a An. IEEE Symp. pe bazele computerului. Sci .. - IEEE Computer Society, 1988. - S. 444-451.
Domnul Garey, D.S. Johnson. Calculatoare și intractabilitate: un ghid pentru teoria NP-completeității . - W.H. Freeman, 1979. - ISBN 0-7167-1044-7 .
H. Saran, V. Vazirani. Găsirea k -tăierilor în intervalul de două ori optim // Proc. a 32-a An. IEEE Symp. pe bazele computerului. Sci . - IEEE Computer Society, 1991. - S. 743-751. Arhivat pe 15 octombrie 2015 la Wayback Machine
Vijay V. Vazirani. Algoritmi de aproximare. - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
N. Guttmann-Beck, R. Hassin. Algoritmi de aproximare pentru minim k -cut // Algorithmica . - 1999. - S. 198-207.
Francesc Comellas, Emily Sapena. Un algoritm multiagent pentru partiţionarea graficelor. Note de curs în Comput. sci. // Algorithmica. - 2006. - T. 3907 . - S. 279-285 . — ISSN 0302-9743 . - doi : 10.1007/s004530010013 . Arhivat din original pe 12 decembrie 2009.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger. Minimum k-cut // Un compendiu de probleme de optimizare NP . — 2000.
W. Fernandez de la Vega, M. Karpinski, C. Mathieu. Scheme de aproximare pentru bisectia metrica si partitionare // Actele celui de-al cincisprezecelea simpozion anual ACM-SIAM despre algoritmi discreti . - 2004. - S. 506-515,.