The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a ca...The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,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 approxima- tion ratio better than0 .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 re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .展开更多
in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MC...in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.展开更多
Suppose that ∏ is a maximization problem,and tha A is an approximation algorithmfor ∏.For every instance I of ∏,define R_A(I)=OPT(I)/A(I),where OPT(I)is the optimal value of I;A(I)is the value of approximate soluti...Suppose that ∏ is a maximization problem,and tha A is an approximation algorithmfor ∏.For every instance I of ∏,define R_A(I)=OPT(I)/A(I),where OPT(I)is the optimal value of I;A(I)is the value of approximate solution given byA,and the performance ratio of algorithm A展开更多
研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(common due window,CDW)条件下,给出一个动态规划算法及一个近似算法;对单机限制性CDW中的某个特殊情况,给出一个多项式时间算法;对两台平行机非限制性CDW情况,构建一个...研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(common due window,CDW)条件下,给出一个动态规划算法及一个近似算法;对单机限制性CDW中的某个特殊情况,给出一个多项式时间算法;对两台平行机非限制性CDW情况,构建一个伪多项式时间动态规划算法,证明其是一般意义下的NP-hard问题.展开更多
基金Supported by the National Natural Science Foundation of China(1 9971 0 78)
文摘The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,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 approxima- tion ratio better than0 .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 re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .
文摘in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.
基金Project supported in part by the National High-tech Project of China.
文摘Suppose that ∏ is a maximization problem,and tha A is an approximation algorithmfor ∏.For every instance I of ∏,define R_A(I)=OPT(I)/A(I),where OPT(I)is the optimal value of I;A(I)is the value of approximate solution given byA,and the performance ratio of algorithm A
文摘研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(common due window,CDW)条件下,给出一个动态规划算法及一个近似算法;对单机限制性CDW中的某个特殊情况,给出一个多项式时间算法;对两台平行机非限制性CDW情况,构建一个伪多项式时间动态规划算法,证明其是一般意义下的NP-hard问题.
