高校应用数学学报B辑
高校應用數學學報B輯
고교응용수학학보B집
APPLIED MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES
2002年
2期
241-250
,共10页
multiple knapsack problem%semi-definite relaxation%approximation algorithm%combinatorial optimization
The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as follows. A set B of n items and a set S of m knapsacks are given such that each item j has a profit pj and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP (B,S,m,n) is strongly NP-Complete and no polynomial-time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,m,n). It is proved that MKPS have a approximation ratio better than 0.5 for a subclass of MKP (B,S,m,n) with n≤100,m≤5 and (maxnj=1{wj})/(minmi=1{Ci})≤(2)/(3).
