On Lagrangian relaxation for constrained maximization and reoptimization problems
| Autor: | Hadas Shachnai, Gal Tamir, Ariel Kulik |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Applied Mathematics
Existential quantification 0211 other engineering and technologies Approximation algorithm 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Maximization 01 natural sciences Scheduling (computing) symbols.namesake 010201 computation theory & mathematics Lagrangian relaxation Independent set symbols Discrete Mathematics and Combinatorics Applied mathematics Generalized assignment problem Mathematics |
| Zdroj: | Discrete Applied Mathematics. 296:164-178 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2020.10.001 |
| Popis: | We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of subset selection problems with linear constraints. Given a problem in this class and some small e ∈ ( 0 , 1 ) , we show that if there exists an r -approximation algorithm for the Lagrangian relaxation of the problem, for some r ∈ ( 0 , 1 ) , then our technique achieves a ratio of r r + 1 − e to the optimal, and this ratio is tight. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the maximum generalized assignment problem (GAP) and maximum weight independent set. For all of the problems studied in this paper, the number of calls to the r -approximation algorithm, used by our algorithms, is linear in the input size and in log ( 1 ∕ e ) for inputs with a cardinality constraint, and polynomial in the input size and in log ( 1 ∕ e ) for inputs with an arbitrary linear constraint. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect