Approximation for multi-knapsack problem  

作　　者：张立昂 李路阳 黄雄 

机构地区：[1]Department of Computer Science and Technology, Peking University, Beijing 100871, China

出　　处：《Chinese Science Bulletin》1996年第12期1042-1045,共4页

基　　金：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

关 键 词：KNAPSACK PROBLEM APPROXIMATION algorithm for combinatorial PROBLEMS COMPUTATIONAL complexity. 

分 类 号：O157[理学—数学]