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_2zbMATH Open1460.90148arXiv2004.08589OpenAlexW3135330276MaRDI QIDQ4965095FDOQ4965095

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)

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.

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

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

zbMATH Keywords

approximate solutioncardinality constraintsmulti-dimensional knapsack problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for knapsack problems with cardinality constraints
• A total-value greedy heuristic for the integer knapsack problem
• 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)