Seminar on Combinatorics

主講者: 李建平教授(雲南大學)
講題: Some Variants of Multiple Knapsack Problem
時間: 2012-02-17 (Fri.)  14:00 - 15:30
地點: 數學所 722 研討室 (台大院區)
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 (Max-Sum MKPB); (ii) the objective is to maximize the minimum profit of a knapsack among these m knapsacks (Max-Min MKPB). We obtain the following results: (1) two variants of the MKPB problem are NP-hard in a strong sense, and for any real number t > 0, the Max-Min 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.
  || Close window ||