Approximation algorithms for the multiple knapsack problem with assignment restrictions

DOI10.1023/A:1009894503716MaRDI QIDQ1583697zbMATH OpenFDO

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)

• Flexible allocation on related machines with assignment restrictions
• Solving the many to many assignment problem by improving the Kuhn-Munkres algorithm with backtracking
• Approximation algorithms for scheduling with reservations
• Distributed approximation of \(k\)-service assignment
• Approximation algorithms for knapsack problems with cardinality constraints
• Emergency relocation of items using single trips: special cases of the multiple knapsack assignment problem
• The food bank resource allocation problem
• Distributed approximation of cellular coverage
• The assignment and loading transportation problem
• Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities
• Algorithms and computational study on a transportation system integrating public transit and ridesharing of personal vehicles
• Coupled-tasks in presence of bipartite compatibilities graphs
• Upper and lower bounding procedures for the multiple knapsack assignment problem
• LP based heuristics for the multiple knapsack problem with assignment restrictions
• Approximability of two variants of multiple knapsack problems
• A branch-and-bound algorithm for the quadratic multiple knapsack problem
• Scheduled service network design with resource management for two-tier multimodal city logistics
• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
• Multiple subset sum with inclusive assignment set restrictions
• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• The influence of the fitness evaluation method on the performance of multiobjective search algorithms
• An efficient approximation for the generalized assignment problem
• A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
• A two-stage model for a day-ahead paratransit planning problem
• An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
• Optimization in production quota problem with convex cost function
• Some complexity and approximation results for coupled-tasks scheduling problem according to topology
• A successive approximation algorithm for the multiple knapsack problem
• Approximate and exact merging of knapsack constraints with cover inequalities
• Airports and railways with unsplittable demand
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583697)