{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T19:07:28Z","timestamp":1707246448810},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T00:00:00Z","timestamp":1657843200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF 18-14613"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"\n Finding locally optimal solutions for\n MAX-CUT<\/jats:sc>\n and\n \n MAX-\n k<\/jats:italic>\n -CUT\n <\/jats:sc>\n 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\u00f6glin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for\n max-cut<\/jats:sc>\n in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for\n max-cut<\/jats:sc>\n in complete graphs is (\n O<\/jats:italic>\n \u03a6\n 5<\/jats:sup>\n n<\/jats:italic>\n 15.1<\/jats:sup>\n ), where \u03a6 is an upper bound on the random edge-weight density and \u03a6 is the number of vertices in the input graph.\n <\/jats:p>\n \n While Angel, Bubeck, Peres, and Wei\u2019s 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 toward improving the run-time bound. We prove that the smoothed complexity of FLIP for\n max-cut<\/jats:sc>\n in complete graphs is\n O<\/jats:italic>\n (\u03a6\n n<\/jats:italic>\n 7.83<\/jats:sup>\n ). 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\n MAX-3-CUT<\/jats:sc>\n in complete graphs is polynomial and for\n MAX<\/jats:sc>\n -\n k<\/jats:italic>\n -\n CUT<\/jats:sc>\n in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest toward showing smoothed polynomial complexity of FLIP for\n MAX<\/jats:sc>\n -\n k<\/jats:italic>\n -\n CUT<\/jats:sc>\n in complete graphs for larger constants\n k<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3454125","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-38","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Improving the Smoothed Complexity of FLIP for Max Cut Problems"],"prefix":"10.1145","volume":"17","author":[{"given":"Ali","family":"Bibak","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign"}]},{"given":"Charles","family":"Carlson","sequence":"additional","affiliation":[{"name":"University of Colorado Boulder"}]},{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana-Champaign"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201917)","author":"Angel O.","unstructured":"O. Angel , S. Bubeck , Y. Peres , and F. Wei . 2017. Local max-cut in smoothed polynomial time . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201917) . 429\u2013437. O. Angel, S. Bubeck, Y. Peres, and F. Wei. 2017. Local max-cut in smoothed polynomial time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201917). 429\u2013437."},{"key":"e_1_2_1_2_1","unstructured":"O. Angel and V. Tassion. 2018. Exponentially long improving sequences for MAX-CUT. Personal Communication. O. Angel and V. Tassion. 2018. Exponentially long improving sequences for MAX-CUT. Personal Communication."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 11th ACM Conference on Electronic Commerce (EC\u201910)","author":"Bhalgat A.","unstructured":"A. Bhalgat , T. Chakraborty , and S. Khanna . 2010. Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games . In Proceedings of the 11th ACM Conference on Electronic Commerce (EC\u201910) . 73\u201382. A. Bhalgat, T. Chakraborty, and S. Khanna. 2010. Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games. In Proceedings of the 11th ACM Conference on Electronic Commerce (EC\u201910). 73\u201382."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920)","author":"Boodaghians S.","unstructured":"S. Boodaghians , R. Kulkarni , and R. Mehta . 2020. Smoothed efficient algorithms and reductions for network coordination games . In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920) . 73:1\u201373:15. S. Boodaghians, R. Kulkarni, and R. Mehta. 2020. Smoothed efficient algorithms and reductions for network coordination games. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920). 73:1\u201373:15."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 38th International Colloquim Conference on Automata, Languages and Programming (ICALP\u201911)","author":"Els\u00e4sser R.","unstructured":"R. Els\u00e4sser and T. Tscheuschner . 2011. Settling the complexity of local max-cut (almost) completely . In Proceedings of the 38th International Colloquim Conference on Automata, Languages and Programming (ICALP\u201911) . 171\u2013182. R. Els\u00e4sser and T. Tscheuschner. 2011. Settling the complexity of local max-cut (almost) completely. In Proceedings of the 38th International Colloquim Conference on Automata, Languages and Programming (ICALP\u201911). 171\u2013182."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201915)","author":"Etscheid M.","unstructured":"M. Etscheid and H. R\u00f6glin . 2015. Smoothed analysis of the squared euclidean maximum-cut problem . In Proceedings of the European Symposium on Algorithms (ESA\u201915) . 509\u2013520. M. Etscheid and H. R\u00f6glin. 2015. Smoothed analysis of the squared euclidean maximum-cut problem. In Proceedings of the European Symposium on Algorithms (ESA\u201915). 509\u2013520."},{"key":"e_1_2_1_7_1","article-title":"Smoothed analysis of local search for the maximum-cut problem","volume":"13","author":"Etscheid M.","year":"2017","unstructured":"M. Etscheid and H. R\u00f6glin . 2017 . Smoothed analysis of local search for the maximum-cut problem . ACM Trans. Algor. 13 , 2, Article 25 (2017), 12 pages. M. Etscheid and H. R\u00f6glin. 2017. Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algor. 13, 2, Article 25 (2017), 12 pages.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904)","author":"Fabrikant A.","unstructured":"A. Fabrikant , C. Papadimitriou , and K. Talwar . 2004. The complexity of pure Nash equilibria . In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904) . 604\u2013612. A. Fabrikant, C. Papadimitriou, and K. Talwar. 2004. The complexity of pure Nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904). 604\u2013612."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523688"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_11_1","unstructured":"J. Kleinberg and \u00c9. Tardos. 2006. Algorithm\u00a0Design. Addison-Wesley. J. Kleinberg and \u00c9. Tardos. 2006. Algorithm\u00a0Design. Addison-Wesley."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3454125","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3454125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T20:47:55Z","timestamp":1672606075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3454125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3454125"],"URL":"https:\/\/doi.org\/10.1145\/3454125","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}