Improving the Smoothed Complexity of FLIP for Max Cut Problems

DOI10.1145/3454125MaRDI QIDQ5032028zbMATH OpenOpenAlexFDO

Authors Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran

Publication date 16 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.05665

zbMATH Keywords

k-cutlocal searchmax-cutsmoothed analysis

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Improving the smoothed complexity of FLIP for max cut problems
• Settling the complexity of local max-cut (almost) completely
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Local max-cut in smoothed polynomial time
• Smoothed analysis of local search for the maximum-cut problem

Cited in

(6)

• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• Smoothed complexity of local max-cut and binary max-CSP
• The smoothed complexity of policy iteration for Markov decision processes
• Local Max-Cut on sparse graphs
• Complexity of local search for Euclidean clustering problems
• Minimum stable cut and treewidth

This page was built for publication: Improving the Smoothed Complexity of FLIP for Max Cut Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032028)