On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint

DOI10.1007/978-3-030-58657-7_2MaRDI QIDQ4965095zbMATH OpenOpenAlexFDO

Authors A. Y. Chirkov, Dmitriy V. Gribanov, N. Yu. Zolotykh

Publication date 25 February 2021

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.08589

zbMATH Keywords

approximate solutioncardinality constraintsmulti-dimensional knapsack problem

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• On the approximation of an optimal solution to the integer knapsack problem by optimal solutions to the integer knapsack problem with a restriction on the cardinality
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximation for multi-knapsack problem
• scientific article; zbMATH DE number 3906236
• Approximation algorithms for knapsack problems with cardinality constraints

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A total-value greedy heuristic for the integer knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Joint performance of greedy heuristics for the integer knapsack problem
• On the approximation of an optimal solution to the integer knapsack problem by optimal solutions to the integer knapsack problem with a restriction on the cardinality

Cited in

(1)

• On the approximation of an optimal solution to the integer knapsack problem by optimal solutions to the integer knapsack problem with a restriction on the cardinality

This page was built for publication: On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4965095)