University of Illinois Urbana-Champaign

Improving the smoothed complexity of flip for max cut problems

Bibaksereshkeh, Seyedali

Content Files
BIBAKSERESHKEH-THESIS-2020.pdf

Permalink

https://hdl.handle.net/2142/108615

Description

Title
Improving the smoothed complexity of flip for max cut problems
Author(s)
Bibaksereshkeh, Seyedali
Issue Date
2020-07-21
Director of Research (if dissertation) or Advisor (if thesis)
Chandrasekaran , Karthekeyan
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2020-10-07T22:44:37Z
Keyword(s)
  • max cut
  • flip
  • graph theory
  • smoothed complexity
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 Roglin [1] showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres and Wei [2] showed that the smoothed complexity of FLIP for maxcut 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, Bubeck, Peres and Wei’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 for max-cut 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.
Graduation Semester
2020-08
Type of Resource
Thesis
Permalink
http://hdl.handle.net/2142/108615
Copyright and License Information
Copyright 2020 SeyedAli BibakSereshkeh

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Industrial and Enterprise Systems Engineering