Approximation algorithms for the multiple knapsack problem with assignment restrictions
From MaRDI portal
Publication:1583697
DOI10.1023/A:1009894503716zbMath0970.90106MaRDI QIDQ1583697
R. Ravi, Milind W. Dawande, Pinar Keskinocak, Jayant R. Kalagnanam, F. Sibel Salman
Publication date: 6 February 2001
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
approximate solutionsmaximizing assigned weightminimizing utilized capacitymultiple knapsack problem with assignment restrictionspolynomial computational time
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (24)
The food bank resource allocation problem ⋮ An efficient approximation for the generalized assignment problem ⋮ Multiple subset sum with inclusive assignment set restrictions ⋮ Coupled-Tasks in Presence of Bipartite Compatibilities Graphs ⋮ LP based heuristics for the multiple knapsack problem with assignment restrictions ⋮ Approximability of Two Variants of Multiple Knapsack Problems ⋮ Some complexity and approximation results for coupled-tasks scheduling problem according to topology ⋮ Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities ⋮ Distributed approximation of cellular coverage ⋮ An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating ⋮ Distributed approximation of \(k\)-service assignment ⋮ Approximate and exact merging of knapsack constraints with cover inequalities ⋮ Scheduled service network design with resource management for two-tier multimodal city logistics ⋮ A \((1-1/e)\)-approximation algorithm for the generalized assignment problem ⋮ Optimization in production quota problem with convex cost function ⋮ The assignment and loading transportation problem ⋮ Approximation algorithms for scheduling with reservations ⋮ Upper and lower bounding procedures for the multiple knapsack assignment problem ⋮ Flexible allocation on related machines with assignment restrictions ⋮ A two-stage model for a day-ahead paratransit planning problem ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ A branch-and-bound algorithm for the quadratic multiple knapsack problem ⋮ The influence of the fitness evaluation method on the performance of multiobjective search algorithms ⋮ A PTAS for the multiple subset sum problem with different knapsack capacities
This page was built for publication: Approximation algorithms for the multiple knapsack problem with assignment restrictions
