Vi beskriver en ny approximationsalgoritm för Max Cut. Vår algoritm körs i Õ(n 2 ) tid, där n är antalet hörn, och uppnår ett approximationsförhållande på.531. I fall där en optimal lösning skär en 1 − ε-fraktion av kanter, finner vår algoritm en lösning som skär en 1−4 ε+ Vårt huvudresultat är en variant av spektral partitionering, som kan genomföras i nästan linjär tid. Med tanke på en graf där Max Cut optimal är en 1 − ε bråkdel av kanter, vår spektral partitionering algoritm finner en uppsättning S av hörn och en bipartition L, R = S − L av S sådan att åtminstone en 1 − O ( ε) bråkdel av kanterna incident på S har en endpoint i L och en endpoint i R. (Detta kan ses som en analog av Cheegers ojämlikhet för den minsta eigenvärde av adjakens matris i en graf.) Initiering av detta förfarande ger de ungefärliga resultat som anges ovan. En annan, mer komplicerad, variant av spektrala partitionering leder till en polynom tid algoritm som skär en 1/2 + e −.(1/ε) bråkdel av kanter i grafer där den optimala är 1/2 + ε.
Trevisan REF föreslog en ungefärlig algoritm för maximal skärning av det minsta eigenvärdet med en approximationsgrad på 0,531.
Max cut and the smallest eigenvalue
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}