Improving the smoothed complexity of FLIP for max cut problems

Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran

Finding locally optimal solutions for max-cut and max-$k$-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP m…