A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
From MaRDI portal
Publication:2494823
DOI10.1016/j.orl.2005.05.006zbMath1110.90065OpenAlexW2028081955MaRDI QIDQ2494823
Raphael Yuster, Israel Beniaminy, Zeev Nutov
Publication date: 30 June 2006
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2005.05.006
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (13)
An efficient approximation for the generalized assignment problem ⋮ Multiple subset sum with inclusive assignment set restrictions ⋮ Approximability of Two Variants of Multiple Knapsack Problems ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ 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 ⋮ Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Scheduling jobs with sizes and delivery times on identical parallel batch machines ⋮ The Complexity of Contracts ⋮ 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 ⋮ Packing items into several bins facilitates approximating the separable assignment problem
Cites Work
This page was built for publication: A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
