### Abstract

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 method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin [ER17] showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres and Wei [ABPW17] showed that the smoothed complexity of FLIP for max-cut in complete graphs is O(φ^{5}n^{15.1}), where φ is an upper bound on the random edge-weight density and n is the number of vertices in the input graph. While Angel et al.’s result showed the first polynomial smoothed complexity, they also conjectured that their run-time bound is far from optimal. In this work, we make substantial progress towards improving the run-time bound. We prove that the smoothed complexity of FLIP in complete graphs is O(φn^{7.83}). Our results are based on a carefully chosen matrix whose rank captures the run-time of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for max-3-cut in complete graphs is polynomial and for max-k-cut in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest towards showing smoothed polynomial complexity of FLIP for max-k-cut in complete graphs for larger constants k.

Original language | English (US) |
---|---|

Pages | 897-916 |

Number of pages | 20 |

State | Published - Jan 1 2019 |

Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019 |

### Conference

Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|

Country | United States |

City | San Diego |

Period | 1/6/19 → 1/9/19 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Improving the smoothed complexity of FLIP for max cut problems'. Together they form a unique fingerprint.

## Cite this

*Improving the smoothed complexity of FLIP for max cut problems*. 897-916. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.