×

On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint. (English) Zbl 1460.90148

Kochetov, Yury (ed.) et al., Mathematical optimization theory and operations research. 19th international conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020. Revised selected papers. Cham: Springer. Commun. Comput. Inf. Sci. 1275, 16-22 (2020).
Summary: We study the proximity of the optimal value of the \(m\)-dimensional knapsack problem to the optimal value of that problem with the additional restriction that only one type of items is allowed to include in the solution. We derive exact and asymptotic formulas for the precision of such approximation, i.e. for the infinum of the ratio of the optimal value for the objective functions of the problem with the cardinality constraint and without it. In particular, we prove that the precision tends to \(0.59136\dots /m\) if \(n\rightarrow \infty\) and \(m\) is fixed. Also, we give the class of the worst multi-dimensional knapsack problems for which the bound is attained. Previously, similar results were known only for the case \(m=1\).
For the entire collection see [Zbl 1454.90004].

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

Knapsack
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints. Eur. J. Oper. Res. 123, 333-345 (2000) · Zbl 0961.90131 · doi:10.1016/S0377-2217(99)00261-1
[2] Chirkov, A.Yu., Shevchenko, V.N.: On the approximation of an optimal solution of the integer knapsack problem by optimal solutions of the integer knapsack problem with a restriction on the cardinality. Diskretn. Anal. Issled. Oper. Ser. 213(2), 56-73 (2006) · Zbl 1249.90169
[3] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24777-7 · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7
[4] Kohli, R., Krishnamurti, R.: A total-value greedy heuristic for the integer knapsack problem. Oper. Res. Lett. 12, 65-71 (1992) · Zbl 0757.90061 · doi:10.1016/0167-6377(92)90065-B
[5] Kohli, R., Krishnamurti, R.: Joint performance of greedy heuristics for the integer knapsack problem. Discrete Appl. Math. 56, 37-48 (1995) · Zbl 0831.90090 · doi:10.1016/0166-218X(93)E0132-I
[6] Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990) · Zbl 0708.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.