On Lagrangian relaxation for constrained maximization and reoptimization problems

DOI10.1016/j.dam.2020.10.001zbMath1464.90098OpenAlexW3110535523MaRDI 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

zbMATH Keywords

Lagrangian relaxationsubset selectionapproximation algorithmsconstrained maximizationcombinatorial reoptimizationset maximization problems

Mathematics Subject Classification ID

Nonlinear programming (90C30) Combinatorial optimization (90C27)

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

This page was built for publication: On Lagrangian relaxation for constrained maximization and reoptimization problems