On Lagrangian Relaxation and Subset Selection Problems

DOI10.1007/978-3-540-93980-1_13zbMATH Open1209.68647arXiv1512.06736OpenAlexW1531196853MaRDI QIDQ3602837FDOQ3602837

Authors: Ariel Kulik, Hadas Shachnai 

Publication date: 12 February 2009

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

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.

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

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