Forschungsinstitut für Diskrete Mathematik

Lecture Module "Advanced Topics In Discrete Mathematics"

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