Maximális vágás
A gráfelméletben és az algoritmusban a maximális vágás olyan vágás, amely legalább annyi élt tartalmaz, mint bármely más vágás. A definíció kiterjesztése az élekhez társított súlyok figyelembevételével történik. Ezután figyelembe vesszük azt a szakaszt, amelynek maximális össztömege van.
A maximális szakaszok hasznos tárgyak, különösen az elméleti fizikában és az elektronikában. De különösen ismertek azokról az algoritmikus problémákról, amelyek egy maximális vágás, általában MAX-CUT elnevezésű , viszonylag jól tanulmányozott probléma megtalálásából állnak, különösen a közelítés összefüggésében .
A tárgy meghatározása és előzetes megjegyzések
Csészék és súlyok
Ha egy grafikon és a széleken lévő súlyok vannak, akkor a vágás csúcsok halmazaként írható le, és a vágás súlya ekkor az élek tömegének összege, amelynek vége ebben a halmazban van, és l másik kívül. A vágás akkor maximális, ha súlya maximális (az összes vágás között).
Különleges eset a maximális kardinalitás szakasza, amely 1-nek megfelelő súlynak felel meg. Ebben az esetben egy szakasz súlya egyszerűen az élek száma.
Megjegyzések
Ne feledje, hogy eleve több maximális vágás lehet, vagyis több különböző vágás, de ugyanaz a kardinális: a maximális kardinális.
Figyelembe vehetjük azt a „iker” objektumot is, amely a minimális vágás , és amelynek teljesen más tulajdonságai vannak, például a flow-max / cut-min tétel adta összefüggést .
Az objektum általánosítása a maximális k- vágás: ekkor már nem két, hanem k összetevőt veszünk figyelembe .
Az algoritmikus probléma meghatározása
Klasszikus meghatározás
A következő kombinatorikus optimalizálási problémát vesszük figyelembe :
Adjon meg egy G grafikont , keressen egy maximális vágást.
És a kapcsolódó döntési probléma :
Adott egy G grafikon és egy k egész szám , van-e legalább k súlyvágás ?
Leginkább a racionális pozitív súlyokat veszik figyelembe.
Írás egyenletben
A probléma megfogalmazható kielégítendő egyenletek formájában. Ez az írás lehetővé teszi, hogy közelebb hozzuk az egyedi játékok sejtésének problémáját azáltal, hogy a kényszer-elégedettség problémaként mutatjuk be .
A gráf minden élénél figyelembe vesszük az egyenletet . A maximális vágás problémája abban áll, hogy bináris hozzárendelést adunk a változóknak , ami maximalizálja az ellenőrzött egyenletek számát.
(xén,xj){\ displaystyle (x_ {i}, x_ {j})}xén-xj=1[2]{\ displaystyle x_ {i} -x_ {j} = 1 [2]}(xén)én{\ displaystyle (x_ {i}) _ {i}}
Pontos felbontás
NP-teljesség
A MAX-CUT döntési probléma NP-teljes . A MAX-CUT optimalizálási probléma NP-nehéz. A verzió, amelyben az élek súlya az egyik Karp a 21 NP-teljes problémák , ahol az egyik teszi a csökkentést a probléma szekvenálása feladatokat az ütemezés , önmagában csökkentette a probléma a hátizsák .
A döntési probléma NP-hiányos marad, ha kordális grafikonokra , osztott grafikonokra (en) , három- és kétoldalas grafikonokra szorítkozunk .
Hatékony algoritmusok speciális esetekhez
A síkgráfok , a problémát meg lehet oldani a polinom időben , mivel ez csapódik le, hogy egy maximális kapcsolási probléma , amely maga is polinom (például a Edmonds algoritmussal ). Ez fontos eredmény az alkalmazások számára.
Sűrű grafikonok esetén meghatározhatunk egy polinomiális idő-közelítő sémát ( PTAS ).
Közelítés
Algoritmusok
Egy nagyon egyszerű valószínűségi algoritmus lehetővé teszi az 1/2 arány megszerzését: minden csomópont önállóan és egységesen választja meg a vágás melyik oldalán lesz. Minden élnek 1/2 valószínűsége van a vágásban, így elvárjuk a maximális vágás értékének legalább a felét. Ezt az algoritmust a feltételes valószínűségi módszer (en) jóvoltából el lehet vonni egy determinisztikus algoritmus megszerzéséhez .
Jobb közelítés érhető el kifinomultabb technikák alkalmazásával. Az algoritmus a Goemans és Williamson, elérését teszi lehetővé, olyan arányban , pontosabban segítségével pozitív semi-definit optimalizálási . Lehetőség van az SDP probléma megoldásának közelítésével gyorsabb algoritmus megszerzésére; ez a közelítés a multiplikatív súly módszer egyik formáját használja .
α≈0,878{\ displaystyle \ alpha \ kb. 0.878}α=2πmin0≤θ≤πθ1-kötözősalátaθ{\ displaystyle \ alpha = {\ tfrac {2} {\ pi}} \ min _ {0 \ leq \ theta \ leq \ pi} {\ tfrac {\ theta} {1- \ cos \ theta}}}
Összetettség és nem közelítés
A problémát nehéz megközelíteni, pontosabban APX-nehéz . Ennek eredményeként nincs PTAS-ja, hacsak P = NP , de vannak állandó arányú közelítő algoritmusok .
Subhash Khot , Guy Kindler, Elchanan Mossel és Ryan O'Donnell kimutatták, hogy feltételezve, hogy az Unique Games Conjecture ( Unique Games Conjecture ) Goemans és Williamson közelítése optimális. Csak azt feltételezve, hogy P különbözik az NP-től , 16/17-es határt kapunk.
Konkrét eset
A sűrű gráfok esetében van egy polinomiális idő közelítési séma .
Egyéb számítási modellek
A problémát streaming algoritmusok szempontjából is tanulmányozták .
Alkalmazások
A maximális vágás meglehetősen természetes objektum, amely a statisztikai fizikában és különösen a nagyon nagyszabású integrációban alkalmazható .
Ising modell
Az egyik alkalmazás az Ising modell , a grafikon csúcsai az atomokat, az élek pedig a jelentős kölcsönhatásokat képviselik. Minden atomnak van egy spinje , felfelé vagy lefelé , majd az interakciók meghatározzák a súlyokat. A maximális vágások ekkor megfelelnek a minimális energiaállapotoknak.
Pinter probléma
Pinternek az a problémája, hogy vezetékeket helyezzen el a lemez mindkét oldalán kereszteződések nélkül, minimalizálva a lemezen keresztező vezetékek számát. Ez a probléma leírható maximális vágási problémaként is.
Bibliográfia
Általános munkák
-
(en) Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela és Marco Protasi , komplexitás és közelítése: Kombinatorikus optimalizálás problémák és Approximability Properties , Springer,2003f
-
Samir Khuller , Balaji Raghavachari és Neal E. Young , „Kapzsi módszerek” , a Közelítő algoritmusok és metaheurisztika kézikönyvében , Chapman,2007.
-
Michael Mitzenmacher és Eli Upfal , Valószínűség és számítás: Randomizált algoritmusok és valószínűségi elemzés , Cambridge,2005.
Cikkek az algoritmikus problémáról
- (en) Subhash Khot , Guy Kindler , Elchanan Mossel és Ryan O'Donnell : „ Optimális megközelíthetlenségi eredmények a MAX-CUT és más 2 változós CSP-k számára? ” , SIAM Journal on Computing , vol. 37, n o 1,2007, P. 319–357 ( DOI 10.1137 / S0097539705447372 )
Az alkalmazásokról
- Frédéric Meunier és Sebo András , „Parcours et coupes ” , in Graphes et applications-vol. 2 , JC Fournier,2007( online olvasás )
Megjegyzések és hivatkozások
-
(a) Vijay Vazirani , approximációs algoritmusok , Springer Verlag , 2001-ben (és 2003), 380 p. ( ISBN 978-3-540-65367-7 ) , fejezet. 2.4 ("Fedélkészlet: gyakorlatok") o. 23 .
-
(a) Vijay Vazirani , approximációs algoritmusok , Springer Verlag , 2001-ben (és 2003), 380 p. ( ISBN 978-3-540-65367-7 ) , fejezet. 26 ("Féloldalas programozás").
-
Ez a megjegyzés van jelen a jegyet a Tim Gowers a Nevanlinna díj 2014. Ő maga idézi nyilatkozatát származó Johan Håstad .
-
(in) Michael Garey és David S. Johnson , Számítógépek és kezelhetetlen: A Guide to the Theory of NP-teljessége , WH Freeman,1979( ISBN 0-7167-1045-5 )
-
Richard M. Karp , „Redukálhatóság a kombinatorikus problémák között” , in Complexity of Computer Computity , Plenum Press,1972, P. 85-103
-
Hans Bodlaender és Klaus Jansen, „A komplexitás a maximális vágási probléma” , a STACS 94 ,
1994, P. 769-780
-
(in) F. Hadlock , " A síkgráf maximális vágásának megtalálása polinomiális időben " , SIAM Journal on Computing , vol. 4,1975, P. 221-225 ( DOI 10,1137 / 0204019 , olvasható online )
-
Lásd a következő cikket, különös tekintettel a "sűrű" pontos meghatározására: (en) Wenceslas Fernandez de la Vega és Marek Karpinski : " A MAX-CUT sűrű súlyozott példányainak polinomiális időbeli közelítése " , Véletlenszerű struktúrák és algoritmusok , John Wiley \ & Sons, Inc., köt. 16, n o 4,2000, P. 314-332.
-
(a) Teofilo F. Gonzalez , Daya Ram Gaur és Ramesh Krishnamurti , Handbook of közelítése Algoritmusok és Metaheuristics , Chapman & Hall / CRC,2007( online olvasás ) , "LP kerekítés és kiterjesztés"szakasz, 4.10.1
-
Eredeti cikk: ( Goemans és Williamson 1995 )
-
Magyarázat magyarul : ( Meunier és Sebo 2007 ).
-
Sanjeev Arora , Elad Hazan és Satyen Kale, „ A multiplikatív súlyok frissítési módszere: meta-algoritmus és alkalmazások ”, Számítási elmélet , vol. 8, n o 1,
2012, P. 121–164 ( online olvasás ).
-
Philip N. Klein és Hsueh-I Lu, „Hatékony közelítési algoritmusok a félig véges programokhoz, amelyek a MAX CUT-ból és a COLORING-ból származnak” , a Számítástechnika huszonnyolcadik éves szimpóziumának folyamata, Philadelphia, Pennsylvania, USA, 1996. május 22–24 .
1996( DOI 10.1145 / 237814.237980 ) , p. 338-347
-
(in) Christos H. Papadimitriou és Mihalis Yannakakis , " Optimalizálás, közelítés és komplexitás osztályok " , Journal of Computer and System Sciences , vol. 43, n o 3,
1991, P. 425-440 ( DOI 10.1016 / 0022-0000 (91) 90023-X )
-
(in) Subhash Khot , Guy Kindler , Elchanan Mossel és Ryan O'Donnell , " Optimális megközelíthetlenségi eredmények a MAX-CUT és más CSP-k 2-változóihoz? ” , SIAM Journal on Computing , vol. 37, n o 1,2007, P. 319–357 ( DOI 10.1137 / S0097539705447372 ).
-
(in) Johan Håstad , " Néhány megközelíthetetlen optimális eredmény " , Journal of the ACM , vol. 48,
2001, P. 798–859 ( DOI 10.1145 / 502090.502098 )
-
(in) Luca Trevisan , Gregory Sorkin , Madhu Szudán és David Williamson , "játékok, közelítés és a lineáris programozás" , a Proceedings of the 37th IEEE Symposium on Foundations of Computer Science ,
2000, P. 617-626.
-
Sanjeev Arora , David R. Karger és Marek Karpinski, „ Polinomiális idő-közelítő rendszerek az NP-nehéz problémák sűrű előfordulásához ”, J. Comput. Syst. Sci. , vol. 58, n o 1,
1999, P. 193-210
-
Michael Kapralov, Sanjeev Khanna és Madhu Sudan , „Alsó határok közvetítése a {MAX-CUT} közelítéséhez” , a Huszonhatodik éves ACM-SIAM szimpózium a diszkrét algoritmusokról (SODA) San Diego, Kalifornia, USA, január 2015. 4–6. ,
2015( online olvasható ) , p. 1263-1282
-
View (in) Francisco Barahona , Martin Grötschel Michael Jünger és Gerhard Reinelt , " A kombinatorikus optimalizálás alkalmazása a statisztikai fizika és az elrendezés tervezési rendszerében " , Operations Research , Vol. 36, n o 3,1988, P. 493-513 ( DOI 10.1287 / op.36.3.493 , JSTOR 170992 ).
-
Ez az alkalmazás ( Meunier és Sebo 2007 ), amely teljesebb magyarázatot tartalmaz.
-
Ezt az alkalmazást először írták le: (-ban) Francisco Barahona , R Maynard , R Rammal és JP Uhry , " Kétdimenziós frusztráció modell alapállapotainak morfológiája " , Journal of Physics A: Matematikai és általános , repülés. 15, n o 21982, P. 673
-
Lásd: Ron Yair Pinter , „ Optimal layer assignment for interconnect ”, Journal of VLSI and computer systems , Computer Science Press, vol. 1, n o 21984, P. 123-137.
-
Lásd ( Meunier és Sebo 2007 ). A "Pinter problem" név szintén ebből a dokumentumból származik.
Külső linkek
-
.
-
A post származó Luca Trevisan blogján a Max vágott, és a kapcsolat spektrális gráfelmélet .
-
Vágás, tenderizálás, szeletelés, csökkentés: kulináris mese a nehéz problémák számítógépes megoldásáról , kulináris metafora a problémáról és annak hozzávetőleges megoldásáról, Nicolas Schabanel és Pierre Pansu, a matematikában folytatódik a robbanás , FSMP, SFS, SMF, SMAI,2013
- Pierre Pansu, " A grafikonok vágása " , a Images des Maths-on ,2011. november 10(megtekintve 2014. június 23-án )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">