On the Smoothed Complexity of Combinatorial Local Search

Yiannis Giannakopoulos, Alexander Grosz, Themistoklis Melissourgos

We propose a unifying framework for smoothed analysis of combinatorial local optimization problems, and show how a diverse selection of problems within the complexity class PLS can…