I detta dokument ger vi bevis som tyder på att MAX-CUT är NP-hård att approximera till inom en faktor av α GW +, för alla > 0, där α GW betecknar det approximationsförhållande som uppnås av Goemans-Williamson algoritm [14], α GW.878567. Detta resultat är villkorat, beroende på två gissningar: a) Unique Games gissning av Khot [24], och b) en mycket trovärdig gissning vi kallar majoritet är Stablest gissning. Dessa resultat indikerar att den geometriska karaktären hos Goemans-Williamson-algoritmen kan vara inneboende i MAX-CUT-problemet. Samma två gissningar innebär också att det är NP-hård till (β + )-ungefärlig MAX-2SAT, där β.943943 är den minsta av (2 + 2 π)/(3 − cos( ska)) på ( π 2, π). Motiverade av våra bevistekniker visar vi att om MAX-2CSP- och MAX-2SAT-problemen är något begränsade - på ett sätt som verkar behålla all sin hårdhet - då har de (α GW − ) och (β − )-tillnärmningsalgoritmer, respektive. Även om vi inte kan bevisa Majority Is Stablest gissningar, ger vi några partiella resultat och anger möjliga riktningar för angrepp. Våra partiella resultat är tillräckligt för att antyda att MAX-CUT är svårt att ( 3 4 + 1 2π + ) - approximate (.909155), förutsatt att endast de unika spelen förmodas. Vi diskuterar också MAX-2CSP problem över non-boolean do- * huvud och ange några relaterade resultat och gissningar. Vi visar till exempel att de unika spelen antyder att det är svårt att approximera MAX-2LIN(q) till inom någon konstant faktor.
De presenterar en 0.878- approximation algoritm, vilket är optimalt förutsatt att den unika spelet Conjecture innehar REF.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
{'venue': '45th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '45th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}