Improving the smoothed complexity of FLIP for max cut problems

Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran

Research output: Contribution to conferencePaper

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(φ5n15.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(φn7.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 languageEnglish (US)
Pages897-916
Number of pages20
StatePublished - Jan 1 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019

Conference

Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
CountryUnited States
CitySan Diego
Period1/6/191/9/19

Fingerprint

Max-cut Problem
Polynomials
Max-cut
Complete Graph
Polynomial
Graph in graph theory
Polynomial Complexity
Exponential time
Arbitrary
Terminate
Discrepancy
Union
Optimal Solution
Tend
Upper bound
Framework

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Bibak, A., Carlson, C., & Chandrasekaran, K. (2019). 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.

Improving the smoothed complexity of FLIP for max cut problems. / Bibak, Ali; Carlson, Charles; Chandrasekaran, Karthekeyan.

2019. 897-916 Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.

Research output: Contribution to conferencePaper

Bibak, A, Carlson, C & Chandrasekaran, K 2019, 'Improving the smoothed complexity of FLIP for max cut problems' Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States, 1/6/19 - 1/9/19, pp. 897-916.
Bibak A, Carlson C, Chandrasekaran K. Improving the smoothed complexity of FLIP for max cut problems. 2019. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.
Bibak, Ali ; Carlson, Charles ; Chandrasekaran, Karthekeyan. / Improving the smoothed complexity of FLIP for max cut problems. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.20 p.
@conference{655f7b73e98a40ad8ad6c5c89d86f207,
title = "Improving the smoothed complexity of FLIP for max cut problems",
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{\"o}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(φ5n15.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(φn7.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.",
author = "Ali Bibak and Charles Carlson and Karthekeyan Chandrasekaran",
year = "2019",
month = "1",
day = "1",
language = "English (US)",
pages = "897--916",
note = "30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 ; Conference date: 06-01-2019 Through 09-01-2019",

}

TY - CONF

T1 - Improving the smoothed complexity of FLIP for max cut problems

AU - Bibak, Ali

AU - Carlson, Charles

AU - Chandrasekaran, Karthekeyan

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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(φ5n15.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(φn7.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.

AB - 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(φ5n15.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(φn7.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.

UR - http://www.scopus.com/inward/record.url?scp=85066962610&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85066962610&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85066962610

SP - 897

EP - 916

ER -