论文标题
关于多维背包问题的最佳值，有或没有基数约束，
On the Proximity of the Optimal Values of the Multi-Dimensional Knapsack Problem with and without the Cardinality Constraint
论文作者
论文摘要
我们研究了M维背包问题的最佳值与该问题的最佳值的近距离，并具有额外的限制，即仅允许一种类型的项目包含在解决方案中。我们为这种近似的精度得出精确和渐近公式，即，对于问题的目标函数的最佳值与基础性约束，没有它。特别是，如果n倾向于无穷大且m是固定的，则证明精度趋于0.59136 .../m。另外，我们给出了达到界限的最糟糕的多维背包问题。以前，仅针对M = 1的情况知道相似的结果。
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.../m if n tends to infinity 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.
