Yutaro Yamaguchi

Finding One Local Optimum Is Easy—but What About Two?

The class PLS (Polynomial Local Search) captures the complexity of finding a solution that is locally optimal and has proven to be an important concept in the theory of local search. It has been shown that local search versions of various combinatorial optimization problems, such as Maximum Independ