Smoothed Complexity of SWAP in Local Graph Partitioning
share
We give the first quasipolynomial upper bound ϕ n^polylog(n) for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width), where n is the number of nodes in the graph and ϕ is a parameter that measures the magnitude of perturbations applied on its edge weights. More generally, we show that the same quasipolynomial upper bound holds for the smoothed complexity of the 2-FLIP algorithm for any binary Maximum Constraint Satisfaction Problem, including local Max-Cut, for which similar bounds were only known for 1-FLIP. Our results are based on an analysis of cycles formed in long sequences of double flips, showing that it is unlikely for every move in a long sequence to incur a positive but small improvement in the cut weight.
READ FULL TEXT