2026-09-22T00:45:10Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/108615 2023-07-11 col_2142_5131 col_2142_16359 com_2142_5130 com_2142_16358 com_2142_234

Chandrasekaran , Karthekeyan Bibaksereshkeh, Seyedali 2020-10-07T22:44:37Z 2020-10-07T22:44:37Z 2022-10-07T22:44:53Z 2020-07-21 2020-08 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. Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-08-01 The student, Seyedali Bibaksereshkeh, accepted the attached license on 2020-07-15 at 10:37. The student, Seyedali Bibaksereshkeh, submitted this Thesis for approval on 2020-07-15 at 10:51. This Thesis was approved for publication on 2020-07-21 at 15:50. DSpace SAF Submission Ingestion Package generated from Vireo submission #15631 on 2020-10-02 at 15:33:22 Made available in DSpace on 2020-10-07T22:44:37Z (GMT). No. of bitstreams: 2 BIBAKSERESHKEH-THESIS-2020.pdf: 449339 bytes, checksum: ec9a83a3d8a9974fef53978c233ddaef (MD5) LICENSE.txt: 4215 bytes, checksum: 486a8b036fe71caef044610afb2912bd (MD5) Previous issue date: 2020-07-21 Embargo set by: Seth Robbins for item 116242 Lift date: 2022-10-07T22:44:53Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system U of I Only application/pdf http://hdl.handle.net/2142/108615 en Copyright 2020 SeyedAli BibakSereshkeh max cut flip graph theory smoothed complexity Improving the smoothed complexity of flip for max cut problems text Thesis Industrial&Enterprise Sys Eng Industrial Engineering University of Illinois at Urbana-Champaign Thesis M.S.