Approximation algorithms for the multiple knapsack problem with assignmentrestrictions

Motivated by a real world application, we study the multiple knapsack probl em with assignment restrictions (MKAR). We are given a set of items, each w ith a positive real weight, and a set of knapsacks, each with a positive re al capacity. In addition, for each item a set of knapsacks that can hold th at item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satis fied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity. We focus on obtaining approximate solutions in polynomial computational tim e. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2 -approximation algorithms: the first one solves single knapsack problems su ccessively and the second one is based on rounding the LP relaxation soluti on. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation a lgorithm.