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

local searchmax-cutsmoothed analysisk-cut

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

(3)

• Smoothed complexity of local max-cut and binary max-CSP
• The smoothed complexity of policy iteration for Markov decision processes
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)

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)