On Lagrangian relaxation for constrained maximization and reoptimization problems
From MaRDI portal
Publication:2664005
DOI10.1016/j.dam.2020.10.001zbMath1464.90098MaRDI QIDQ2664005
Ariel Kulik, Hadas Shachnai, Gal Tamir
Publication date: 20 April 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2020.10.001
Lagrangian relaxation; subset selection; approximation algorithms; constrained maximization; combinatorial reoptimization; set maximization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A bicriteria approach to robust optimization
- Reoptimization of maximum weight induced hereditary subgraph problems
- Budgeted matching and budgeted matroid intersection via the gasoline puzzle
- A unified approach to approximating partial covering problems
- Reoptimization of the shortest common superstring problem
- An efficient approximation for the generalized assignment problem
- Real-time scheduling with a budget
- Resource allocation in bounded degree trees
- Multiple and bicriteria scheduling: A literature survey
- A theory and algorithms for combinatorial reoptimization
- Derandomized graph products
- Reoptimization in machine scheduling
- An overview of bilevel optimization
- Approximating the Throughput of Multiple Machines in Real-Time Scheduling
- Tight Approximation Algorithms for Maximum Separable Assignment Problems
- New Advances in Reoptimizing the Minimum Steiner Tree Problem
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems
- The constrained minimum spanning tree problem
- Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Reoptimization of NP-Hard Problems
