An efficient approximation for the generalized assignment problem
From MaRDI portal
Publication:845859
DOI10.1016/j.ipl.2006.06.003zbMath1185.68853MaRDI 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
68W25: Approximation algorithms
Related Items
Online Submodular Maximization with Preemption, Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays, Constrained Submodular Maximization via a Nonsymmetric Technique, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, A Novel Approximate Algorithm for Admission Control, A Survey of the Generalized Assignment Problem and Its Applications, The generalized assignment problem with minimum quantities, The equilibrium generalized assignment problem and genetic algorithm, Distributed approximation of cellular coverage, Improved approximation algorithms for box contact representations, Performance bounds with curvature for batched greedy optimization, The generalized maximum coverage problem, Distributed approximation of \(k\)-service assignment, Flexible allocation on related machines with assignment restrictions, Solving the weighted capacitated planned maintenance problem and its variants, Submodular optimization problems and greedy strategies: a survey, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, A priority based unbalanced time minimization assignment problem, 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, Knapsack problems with sigmoid utilities: approximation algorithms via hybrid optimization, Task assignment in tree-like hierarchical structures, On Lagrangian relaxation for constrained maximization and reoptimization problems, Approximation algorithms for the generalized incremental knapsack problem, Approximability of Two Variants of Multiple Knapsack Problems, Two stage decision making approach for Sensor Mission Assignment Problem, Tight Approximation Bounds for the Seminar Assignment Problem, A Polynomial Time Approximation Scheme for the Square Packing Problem, On Lagrangian Relaxation and Subset Selection Problems
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
