多背包问题近似计算的复杂性  

作　　者：张立昂[1] 李路阳 黄雄 

机构地区：[1]北京大学计算机科学技术系,北京100871

出　　处：《科学通报》1996年第20期1896-1898,共3页Chinese Science Bulletin

基　　金：国家"八六三"计划资助项目

摘　　要：设Π是最大化问题,A是关于Π的近似算法。对Π的每一个实例I,记 R_A(I)=OPT(I)/A(I), 其中OPT(I)是I的最优值,A(I)是算法A求得的近似解的值。记 R_A=inf{4r≥1:对所有的实例I,R_A(I)≤r}, R_A称作A的性能比。如果及_A<+∞,则称A具有常数比。

关 键 词：背包问题 组合优化 近似算法 复杂性 

分 类 号：O224[理学—运筹学与控制论]