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)

zbMATH Keywords

approximate solutionsmaximizing assigned weightminimizing utilized capacitymultiple knapsack problem with assignment restrictionspolynomial computational time

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Approximability of two variants of multiple knapsack problems
• Upper and lower bounding procedures for the multiple knapsack assignment problem
• LP based heuristics for the multiple knapsack problem with assignment restrictions
• Publication:4952619
• Approximation for multi-knapsack problem

Cited In (31)

• 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
• Coupled-tasks in presence of bipartite compatibilities graphs
• 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
• Emergency relocation of items using single trips: special cases of the multiple knapsack assignment problem
• Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities
• Approximability of two variants of multiple knapsack problems
• 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
• 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
• 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)