Abstract:
 Given m knapsacks with different capacities and a restricted bipartite graph G=(S∪T;E), where each vertex vi ?S∪T presents an item i with a size si and a profit pi, the two items i and j may be packed into same knapsack only when the two vertices vi and vj are adjacent in G, and for 1≦k≦m, the profit of each knapsack bk is defined as the total profit of the items packed into that knapsack bk. We consider two variants of the multiple knapsack problem with restricted bipartite graph in the following versions: (i) the objective is to maximize the total profit of items packed in m knapsacks (MaxSum MKPB); (ii) the objective is to maximize the minimum profit of a knapsack among these m knapsacks (MaxMin MKPB). We obtain the following results: (1) two variants of the MKPB problem are NPhard in a strong sense, and for any real number t > 0, the MaxMin MKPB problem cannot be approximated within a factor 1/2 + t; (2) we design two approximation algorithms to solve these two variants of the MKPB problem, respectively; (3) we finally present two optimal algorithms to solve them for the cases where all knapsacks have the same capacity, respectively.
