Improving the Smoothed Complexity of FLIP for Max Cut Problems

DOI10.1145/3454125OpenAlexW3185749561MaRDI QIDQ5032028FDOQ5032028

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

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

zbMATH Keywords

local searchmax-cutsmoothed analysisk-cut

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (3)

• Smoothed complexity of local max-cut and binary max-CSP
• Title not available (Why is that?)
• The smoothed complexity of policy iteration for Markov decision processes

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)