Maximální řez - Maximum cut

Příklad maximálního řezu

Pro graf, a maximální řez je střih jehož velikost je alespoň velikostí jakéhokoli jiného střihu. To znamená, že se jedná o rozdělení vrcholů grafu do dvou doplňkových sad S a T, takže počet hran mezi sadou S a sada T je co největší. Problém nalezení maximálního řezu v grafu je známý jako Problém Max-Cut.

Problém lze uvést jednoduše následovně. Jeden chce podmnožinu S vrcholu nastavena tak, aby počet hran mezi S a doplňková podmnožina je co největší. Ekvivalentně, jeden chce bipartitní podgraf grafu s co největším počtem hran.

Existuje obecnější verze problému s názvem vážený Max-Cut, kde každá hrana je spojena se skutečným číslem, je hmotnosta cílem je maximalizovat celkovou hmotnost hran mezi nimi S a jeho doplněk, spíše než počet okrajů. Vážený problém Max-Cut umožňující pozitivní i negativní váhy lze triviálně transformovat na vážený minimální řez překlopením cedule ve všech vahách.

Výpočetní složitost

Následující rozhodovací problém týkající se maximálních škrtů bylo široce studováno v teoretická informatika:

Daný graf G a celé číslo k, určete, zda existuje alespoň velikost k v G.

O tomto problému je známo NP-kompletní. Je snadno vidět, že problém je v NP: a Ano odpověď lze snadno dokázat předložením dostatečně velkého řezu. NP-úplnost problému lze ukázat například snížením z maximální uspokojivost 2 (omezení problém maximální uspokojivosti ).^[1] Vážená verze rozhodovacího problému byla jedna z Karpových 21 NP-úplných problémů;^[2] Karp ukázal NP-úplnost snížením od problém s oddílem.

Kanonický varianta optimalizace výše uvedeného rozhodovacího problému je obvykle známý jako Problém maximálního řezu nebo Max. Řez a je definována jako:

Daný graf G, najděte maximální řez.

O variantě optimalizace je známo, že je NP-Hard. Opačný problém, a to hledání minimální řez je známo, že je účinně řešitelný prostřednictvím Algoritmus Ford-Fulkerson.

Algoritmy

Algoritmy polynomiálního času

Jak je problém Max-Cut NP-tvrdé, nejsou známy žádné algoritmy polynomiálního času pro Max-Cut v obecných grafech.

Rovinné grafy

Nicméně v rovinné grafy, Problém s maximálním řezem je dvojí problém kontroly trasy (problém najít nejkratší prohlídku, která alespoň jednou navštíví každou hranu grafu), v tom smyslu, že hrany, které nepatří do maximální sestavy grafu G jsou duály hran, které jsou zdvojnásobeny při optimální inspekční prohlídce duální graf z G. Optimální inspekční prohlídka tvoří křižovatku, která se protíná, a rozděluje rovinu na dvě podmnožiny, podmnožinu bodů, pro které číslo vinutí křivky je sudá a podmnožina, pro kterou je číslo vinutí liché; tyto dvě podmnožiny tvoří střih, který zahrnuje všechny hrany, jejichž duály se v prohlídce objevují lichě. Problém kontroly trasy může být vyřešen v polynomiálním čase a tato dualita umožňuje také řešení problému maximálního řezu v polynomiálním čase pro rovinné grafy.^[3] Je známo, že problém Maximum-Bisection je NP-těžký.^[4]

Aproximační algoritmy

Problém Max-Cut je APX-tvrdé,^[5] což znamená, že neexistuje žádné polynomiálně-časové aproximační schéma (PTAS), libovolně blízké optimálnímu řešení, pokud P = NP. Každý známý algoritmus aproximace v polynomiálním čase tedy dosahuje přibližný poměr přísně méně než jeden.

Existuje jednoduchý náhodně 0.5-aproximační algoritmus: pro každý vrchol otočte mincí, abyste se rozhodli, které polovině oddílu ji přiřadíte.^[6][7] V očekávání jsou poloviny okrajů řezané hrany. Tento algoritmus může být derandomizováno s metoda podmíněných pravděpodobností; proto existuje také jednoduchý deterministický algoritmus polynomiálního času s 0,5 aproximací.^[8][9] Jeden takový algoritmus začíná libovolným rozdělením vrcholů daného grafu ${displaystyle G = (V, E)}$ a opakovaně přesouvá jeden vrchol najednou z jedné strany přepážky na druhou a vylepšuje řešení v každém kroku, dokud již nelze provést další vylepšení tohoto typu. Počet iterací je maximálně ${displaystyle | E |}$ protože algoritmus zlepšuje řez o alespoň jednu hranu v každém kroku. Když se algoritmus ukončí, alespoň polovina okrajů dopadajících na každý vrchol patří řezu, protože jinak by pohyb vrcholem vylepšil řez. Proto řez zahrnuje alespoň ${displaystyle | E | / 2}$ hrany.

Algoritmus aproximace polynomiálního času pro Max-Cut s nejznámějším aproximačním poměrem je metoda Goemansa a Williamsona používající semidefinitní programování a náhodné zaokrouhlování který dosahuje přibližného poměru ${displaystyle alpha cca 0,878,}$ kde

${displaystyle alpha = {frac {2} {pi}} min _ {0leq heta leq pi} {frac {heta} {1-cos heta}}.}$^[10][11]

Pokud domněnky o jedinečných hrách je pravda, toto je nejlepší možný poměr přiblížení pro maximální řez.^[12] Bez těchto neprokázaných předpokladů se ukázalo, že je těžké NP odhadnout hodnotu maximálního řezu s přibližným poměrem lepším než ${displaystyle {frac {16} {17}} přibližně 0,941}$.^[13][14]

v ^[15] k tomuto problému existuje rozšířená analýza 10 heuristik, včetně implementace open-source.

Aplikace

Teoretická fyzika

v statistická fyzika a neuspořádané systémy, problém Max Cut je ekvivalentní minimalizaci Hamiltonian a točit sklo model, nejjednodušší model Isingův model.^[16] Pro Isingův model na grafu G a pouze interakce nejbližšího souseda je Hamiltonian

${displaystyle H [s] = - součet _ {ijin E (G)} J_ {ij} s_ {i} s_ {j}}$

Tady každý vrchol i grafu je místo rotace, které může nabrat hodnotu rotace ${displaystyle s_ {i} = odpoledne 1.}$ Oddíly konfigurace rotace ${displaystyle V (G)}$ do dvou sad, ti se točí ${displaystyle V ^ {+}}$ a ti, kteří mají spánek ${displaystyle V ^ {-}.}$ Označujeme s ${displaystyle delta (V ^ {+})}$ sada hran, které spojují dvě sady. Potom můžeme přepsat Hamiltonian jako

${displaystyle {egin {aligned} H [s] & = - součet _ {ijin E (V ^ {+})} J_ {ij} -sum _ {ijin E (V ^ {-})} J_ {ij} + součet _ {ijin delta (V ^ {+})} J_ {ij} & = - součet _ {ijin E (G)} J_ {ij} + 2sum _ {ijin delta (V ^ {+})} J_ { ij} & = C + 2sum _ {delta ijin (V ^ {+})} J_ {ij} konec {zarovnáno}}}$

Minimalizace této energie je ekvivalentní problému min-cut nebo nastavením vah grafu jako ${displaystyle w_ {ij} = - J_ {ij},}$ problém maximálního řezu.^[16]

Návrh obvodu

Problém s maximálním řezem má aplikace v VLSI design.^[16]

Viz také

• Minimální řez
• Minimální k-řez
• Lichý cyklus příčný, což odpovídá požadavku na největší bipartitu indukovaný podgraf

Poznámky

Reference

• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Složitost a aproximace: Problémy kombinatorické optimalizace a vlastnosti jejich přibližnostiSpringer.

Maximální řez (optimalizační verze) je problém ND14 v příloze B (strana 399).

• Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN  978-0-7167-1045-5.

Maximum cut (decision version) is the problem ND16 in Annex A2.2.

Maximální bipartitní podgraf (rozhodovací verze) je problém GT25 v dodatku A1.2.

• Gaur, Daya Ram; Krishnamurti, Ramesh (2007), "Zaokrouhlování a rozšíření LP", v Gonzalez, Teofilo F. (vyd.), Příručka aproximačních algoritmů a metheuristiky, Chapman & Hall / CRC.
• Goemans, Michel X.; Williamson, David P. (1995), „Vylepšené aproximační algoritmy pro problémy maximálního řezu a uspokojivosti pomocí semidefinitního programování“, Deník ACM, 42 (6): 1115–1145, doi:10.1145/227683.227684, S2CID  15794408.
• Hadlock, F. (1975), „Hledání maximálního řezu rovinného grafu v polynomiálním čase“, SIAM J. Comput., 4 (3): 221–225, doi:10.1137/0204019.
• Håstad, Johan (2001), „Některé optimální výsledky přibližnosti“, Deník ACM, 48 (4): 798–859, doi:10.1145/502090.502098, S2CID  5120748.
• Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike (2005), „Schémata polynomiálního přibližování času pro MAX-BISECTION na rovinných a geometrických grafech“, SIAM Journal on Computing, 35 (1): 110–119, CiteSeerX  10.1.1.62.5082, doi:10.1137 / s009753970139567x.
• Karp, Richard M. (1972), "Redukovatelnost mezi kombinatorickými problémy ", Miller, R. E.; Thacher, J. W. (eds.), Složitost počítačového výpočtu, Plenum Press, str. 85–103.
• Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "Optimální výsledky v oblasti nepřístupnosti pro MAX-CUT a další 2-proměnné CSP?", SIAM Journal on Computing, 37 (1): 319–357, doi:10.1137 / S0097539705447372.
• Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), „Chamtivé metody“, Gonzalez, Teofilo F. (ed.), Příručka aproximačních algoritmů a metheuristiky, Chapman & Hall / CRC.
• Mitzenmacher, Michael; Upfal, Eli (2005), Pravděpodobnost a výpočet: Randomizované algoritmy a pravděpodobnostní analýza, Cambridge.
• Motwani, Rajeev; Raghavan, Prabhakar (1995), Randomizované algoritmy, Cambridge.
• Newman, Alantha (2008), „Max cut“, v Kao, Ming-Yang (ed.), Encyclopedia of Algorithms, Springer, str. 489–492, doi:10.1007/978-0-387-30162-4_219, ISBN  978-0-387-30770-1.
• Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), „Třídy optimalizace, aproximace a složitosti“, Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016 / 0022-0000 (91) 90023-X.
• Trevisan, Luca; Sorkin, Gregory; Súdán, Madhu; Williamson, David (2000), „Gadgety, aproximace a lineární programování“, Proceedings of the 37.th IEEE Symposium on Foundations of Computer Science: 617–626.
• Dunning, Iain; Gupta, Swati; Silberholz, John (2018), "Co funguje nejlépe, když? Systematické hodnocení heuristiky pro Max-Cut a QUBO", INFORMS Journal o práci na počítači, 30 (3): 608–624, doi:10.1287 / ijoc.2017.0798.

externí odkazy

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), „Maximum Cut“, v „Kompendium problémů s optimalizací NP“.
• Andrea Casini, Nicola Rebagliati (2012), „Knihovna Pythonu pro řešení Max Cut