On Lagrangian Relaxation and Subset Selection Problems

DOI10.1007/978-3-540-93980-1_13MaRDI QIDQ3602837zbMATH OpenOpenAlexFDO

Authors Ariel Kulik, Hadas Shachnai

Publication date 12 February 2009

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06736

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Nonlinear programming (90C30) Approximation algorithms (68W25)

Abstract: 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 {em subset selection} problems with linear constraints. Given a problem in this class and some small $epsin(0,1)$, we show that if there exists an $r$-approximation algorithm for the Lagrangian relaxation of the problem, for some $rin(0,1)$, then our technique achieves a ratio of $fracrr+1-!eps$ to the optimal, and this ratio is tight. The number of calls to the $r$-approximation algorithm, used by our algorithms, is {em linear} in the input size and in $log(1/eps)$ for inputs with cardinality constraint, and polynomial in the input size and in $log(1/eps)$ for inputs with arbitrary linear constraint. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the {em maximum generalized assignment problem (GAP)} and maximum weight independent set.

Recommendations

• On Lagrangian relaxation for constrained maximization and reoptimization problems
• Lagrangian relaxation and partial cover (Extended abstract)
• scientific article; zbMATH DE number 4199945
• Multi-constrained matroidal knapsack problems
• Lagrangean/surrogate relaxation for generalized assignment problems

Cites work

• scientific article; zbMATH DE number 1182757 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A Unified Approach to Approximating Partial Covering Problems
• A unified approach to approximating resource allocation and scheduling
• An efficient approximation for the generalized assignment problem
• Approximating the throughput of multiple machines in real-time scheduling
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Derandomized graph products
• On Lagrangian Relaxation and Subset Selection Problems
• Real-time scheduling with a budget
• Resource Allocation in Bounded Degree Trees
• Tight approximation algorithms for maximum general assignment problems

Cited in

(8)

• The Lagrangian relaxation for the combinatorial integral approximation problem
• Solving the swath segment selection problem through Lagrangean relaxation
• Network pollution games
• On Lagrangian Relaxation and Subset Selection Problems
• Lagrangian relaxation and partial cover (Extended abstract)
• On Lagrangian relaxation for constrained maximization and reoptimization problems
• New bounds for subset selection from conic relaxations
• The sublinear operator method and selector problems

This page was built for publication: On Lagrangian Relaxation and Subset Selection Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602837)