Att hitta lokalt optimala lösningar för max-cut och max-k-cut är välkända PLS-kompletta problem. Ett instinktivt tillvägagångssätt för att hitta en sådan lokalt optimal lösning är FLIP-metoden. Även om FLIP kräver exponentiell tid i värsta fall, tenderar det att avslutas snabbt i praktiska fall. För att förklara denna diskrepans har drifttiden för FLIP undersökts inom ramen för den utjämnade komplexiteten. Etscheid och Röglin [ER17] visade att den utjämnade komplexiteten hos FLIP för maximal klippning i godtyckliga grafer är kvasipolynomiell. Angel, Bubeck, Peres och Wei [ABPW17] visade att den utjämnade komplexiteten hos FLIP för max-cut i kompletta grafer är O (5 n 15.1 ), där en övre gräns på random egg-vikt densitet och n är antalet hörn i inmatningskurvan. Medan Angel et al.Resultatet visade den första polynom slätade komplexiteten, de antog också att deras körtid gräns är långt ifrån optimal. I detta arbete gör vi betydande framsteg när det gäller att förbättra tidsgränsen. Vi bevisar att den utjämnade komplexiteten av FLIP i kompletta grafer är O(en 7.83 ). Våra resultat är baserade på en noggrant vald matris vars rang fångar run-time av metoden tillsammans med förbättrade rank gränser för denna matris och en förbättrad förening bundet baserat på denna matris. Dessutom ger våra tekniker en allmän ram för att analysera FLIP i det utjämnade ramverket. Vi illustrerar denna allmänna ram genom att visa att den utjämnade komplexiteten hos FLIP för max-3-cut i kompletta grafer är polynom och för max-k-cut i godtyckliga grafer är kvasi-polynomial. Vi anser att våra tekniker också bör vara av intresse för att ta itu med den utjämnade komplexiteten hos FLIP för max-k-cut i kompletta grafer för större konstanter k.
Oberoende, Bibaksereshkeh, Carlson, och Chandrasekaran REF förbättrade körtiden för den lokala-max-cut algoritm, och erhöll utjämnade polynomial och kvasi-polynomial algoritmer för lokal-3-cut och lokal-k-cut med konstant k respektive.
Improving the smoothed complexity of FLIP for max cut problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}