Approximation algorithms for the multiple knapsack problem with assignment restrictions
DOI10.1023/A:1009894503716zbMATH Open0970.90106MaRDI QIDQ1583697FDOQ1583697
Authors: R. Ravi, Milind Dawande, Jayant Kalagnanam, Pinar Keskinocak, F. Sibel Salman 
Publication date: 6 February 2001
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Recommendations
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)
Cited In (30)
- The food bank resource allocation problem
- LP based heuristics for the multiple knapsack problem with assignment restrictions
- Distributed approximation of \(k\)-service assignment
- Multiple subset sum with inclusive assignment set restrictions
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- An efficient approximation for the generalized assignment problem
- Approximation algorithms for scheduling with reservations
- Distributed approximation of cellular coverage
- A branch-and-bound algorithm for the quadratic multiple knapsack problem
- Solving the many to many assignment problem by improving the Kuhn-Munkres algorithm with backtracking
- A two-stage model for a day-ahead paratransit planning problem
- A successive approximation algorithm for the multiple knapsack problem
- Approximate and exact merging of knapsack constraints with cover inequalities
- A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
- Approximation algorithms for knapsack problems with cardinality constraints
- Optimization in production quota problem with convex cost function
- Flexible allocation on related machines with assignment restrictions
- Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities
- Some complexity and approximation results for coupled-tasks scheduling problem according to topology
- A PTAS for the multiple subset sum problem with different knapsack capacities
- The assignment and loading transportation problem
- Airports and railways with unsplittable demand
- Coupled-Tasks in Presence of Bipartite Compatibilities Graphs
- A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- Upper and lower bounding procedures for the multiple knapsack assignment problem
- Algorithms and computational study on a transportation system integrating public transit and ridesharing of personal vehicles
- Scheduled service network design with resource management for two-tier multimodal city logistics
- The influence of the fitness evaluation method on the performance of multiobjective search algorithms
- Approximability of Two Variants of Multiple Knapsack Problems
- An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
This page was built for publication: Approximation algorithms for the multiple knapsack problem with assignment restrictions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583697)
