On Lagrangian relaxation for constrained maximization and reoptimization problems

DOI10.1016/J.DAM.2020.10.001zbMATH Open1464.90098OpenAlexW3110535523MaRDI QIDQ2664005FDOQ2664005

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

Recommendations

• On Lagrangian Relaxation and Subset Selection Problems
• scientific article
• A new Lagrangian relaxation approach to the generalized assignment problem
• scientific article; zbMATH DE number 2084780
• The omnipresence of Lagrange

zbMATH Keywords

approximation algorithmsLagrangian relaxationsubset selectionconstrained maximizationcombinatorial reoptimizationset maximization problems

Mathematics Subject Classification ID

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

Cites Work

• An overview of bilevel optimization
• Tight approximation algorithms for maximum separable assignment problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The constrained minimum spanning tree problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• An efficient approximation for the generalized assignment problem
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Title not available (Why is that?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Derandomized graph products
• Reoptimization in machine scheduling
• 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
• A unified approach to approximating partial covering problems
• Complexity and approximation in reoptimization
• A bicriteria approach to robust optimization
• Multiple and bicriteria scheduling: A literature survey
• Reoptimization of maximum weight induced hereditary subgraph problems
• Reoptimization of the shortest common superstring problem
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Title not available (Why is that?)
• New Advances in Reoptimizing the Minimum Steiner Tree Problem
• Reoptimization of NP-Hard Problems
• Title not available (Why is that?)
• A theory and algorithms for combinatorial reoptimization
• Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems

Cited In (4)

• A lagrangean relaxation algorithm for the constrained matrix problem
• On Lagrangian Relaxation and Subset Selection Problems
• Principles and Practice of Constraint Programming – CP 2004
• Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs

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

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