Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
Lukas Michel, Alex Scott
Local search algorithms for NP-hard problems such as Max-Cut frequently perform much better in practice than worst-case analysis suggests. Smoothed analysis has proved an effective…
cs.DS2024
Lower bounds for graph reconstruction with maximal independent set queries
Lukas Michel, Alex Scott
We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least $Ω(Î^2…