An efficient approximation for the generalized assignment problem
From MaRDI portal
Publication:845859
DOI10.1016/j.ipl.2006.06.003zbMath1185.68853OpenAlexW2158760370MaRDI QIDQ845859
Liran Katzir, Danny Raz, Reuven Cohen
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2006.06.003
Related Items
A Novel Approximate Algorithm for Admission Control ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ Task assignment in tree-like hierarchical structures ⋮ Approximability of Two Variants of Multiple Knapsack Problems ⋮ Two stage decision making approach for Sensor Mission Assignment Problem ⋮ A Polynomial Time Approximation Scheme for the Square Packing Problem ⋮ Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ The equilibrium generalized assignment problem and genetic algorithm ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Distributed approximation of cellular coverage ⋮ Tight Approximation Bounds for the Seminar Assignment Problem ⋮ Distributed approximation of \(k\)-service assignment ⋮ Solving the weighted capacitated planned maintenance problem and its variants ⋮ Improved approximation algorithms for box contact representations ⋮ The generalized maximum coverage problem ⋮ On Lagrangian Relaxation and Subset Selection Problems ⋮ Performance bounds with curvature for batched greedy optimization ⋮ Flexible allocation on related machines with assignment restrictions ⋮ Online Submodular Maximization with Preemption ⋮ A priority based unbalanced time minimization assignment problem ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ Minimizing machine assignment costs over \(\Delta\)-approximate solutions of the scheduling problem \(P||C_{\max}\) ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem ⋮ The generalized assignment problem with minimum quantities ⋮ Knapsack problems with sigmoid utilities: approximation algorithms via hybrid optimization
Uses Software
Cites Work
- An approximation algorithm for the generalized assignment problem
- Approximation algorithms for the multiple knapsack problem with assignment restrictions
- Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
- A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
- Tight approximation algorithms for maximum general assignment problems
- Fast Approximation Algorithms for Knapsack Problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A unified approach to approximating resource allocation and scheduling
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
