Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
This work provides a theoretical framework for improving approximation guarantees in combinatorial optimization, particularly for sparse optimization problems, but it is incremental as it builds on existing local search methods.
The paper tackles the problem of analyzing approximation guarantees for local search algorithms in combinatorial optimization by introducing a new notion called localizability of set functions. It applies this framework to sparse optimization, showing that restricted strong concavity and smoothness imply localizability, and develops accelerated local search algorithms with experimental validation in sparse regression and graphical model structure learning.
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 various combinatorial optimization problems. To analyze local search algorithms for set function maximization, we propose a new notion called localizability of set functions, which measures how effective local improvement is. Moreover, we provide approximation guarantees of standard local search algorithms under various combinatorial constraints in terms of localizability. The main application of our framework is sparse optimization, for which we show that restricted strong concavity and restricted smoothness of the objective function imply localizability, and further develop accelerated versions of local search algorithms. We conduct experiments in sparse regression and structure learning of graphical models to confirm the practical efficiency of the proposed local search algorithms.