Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions

Kaito Fujii

This paper proposes a new framework for providing approximation guarantees of local search algorithms. Local search is a basic algorithm design technique and is widely used for var…