Smoothed Complexity of SWAP in Local Graph Partitioning
Preprint
Abstract
We give the first quasipolynomial upper bound $φn^{\text{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.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Smoothed Analysis of Local Search for the Maximum-Cut ProblemACM Transactions on Algorithms, 2017
- Smoothed Analysis of the 2-Opt Algorithm for the General TSPACM Transactions on Algorithms, 2016
- Smoothed analysis of symmetric random matrices with continuous distributionsProceedings of the American Mathematical Society, 2015
- Smoothed Analysis of the k-Means MethodJournal of the ACM, 2011
- Smoothed analysis of integer programmingMathematical Programming, 2007
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph PartitioningOperations Research, 1989
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970