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

【摘要】 <正>设Π是最大化问题,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具有常数比。关于Π的多项式时间近似方案更多还原