Summer Term 2023
Local Search Algorithms
We discuss the technique of local search from various points of view. Among others, we present several examples of its use in approximation algorithms for hard combinatorial optimization problems; we briefly look into variants of local search that are used in practical applications; and we discuss local search from a complexity theory perspective, introducing the class PLS together with PLS reductions and the concept of PLS completeness.
Prof. Dr. S. Hougardy,
Dr. M. Nägele