Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε. © 1976.
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Khaled A.S. Abdel-Ghaffar
IEEE Trans. Inf. Theory
Pradip Bose
VTS 1998
Joel L. Wolf, Mark S. Squillante, et al.
IEEE Transactions on Knowledge and Data Engineering