On the Proximity of the Optimal Values of the Multi-dimensional Knapsack Problem with and Without the Cardinality Constraint

Чирков А. Ю.; D. Gribanov; N. Zolotykh

doi:10.1007/978-3-030-58657-7_2

Publications

?

On the Proximity of the Optimal Values of the Multi-dimensional Knapsack Problem with and Without the Cardinality Constraint

P. 16–22.

Чирков А. Ю., Gribanov D., Zolotykh N.

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→∞ 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.

Language: English

DOI

Text on another site

Keywords: Multi-dimensional knapsack problem Approximate solution Cardinality constraints

In book

Mathematical Optimization Theory and Operations Research, 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, (Т. 12095)

Cham: Springer, 2020.

On lattice point counting in Δ-modular polyhedra

Gribanov D., Zolotykh N., Optimization Letters 2022 Vol. 16 No. 7 P. 1991–2018

Let a polyhedron $P$ be defined by one of the following ways: \begin{enumerate} \item[(i)] $P = \{x \in \RR^n \colon A x \leq b\}$, where $A \in \ZZ^{(n+k) \times n}$, $b \in \ZZ^{(n+k)}$ and $\rank A = n$, \item[(ii)] $P = \{x \in \RR_+^n \colon A x = b\}$, where $A \in \ZZ^{k \times n}$, $b \in \ZZ^{k}$ ...

Added: October 29, 2021

An FPTAS for the Δ-Modular Multidimensional Knapsack Problem

Gribanov D., , in: Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings.: Cham: Springer, 2021. P. 79–95.

Added: October 29, 2021

Approximations to the solution of Cauchy problem for a linear evolution equation via the space shift operator (second-order equation example)

Remizov I., Applied Mathematics and Computation 2018 Vol. 328 P. 243–246

We present a general method of solving the Cauchy problem for a linear parabolic partial differential equation of evolution type with variable coefficients and demonstrate it on the equation with derivatives of orders two, one and zero. The method is based on the Chernoff approximation procedure applied to a specially constructed shift operator. It is ...

Added: May 25, 2018

A human learning optimization algorithm and its application to multi-dimensional knapsack problems

Wang L., Yang R., Ni H. et al., Applied Soft Computing Journal 2015 Vol. 34 P. 736–743

Inspired by human learning mechanisms, a novel meta-heuristic algorithm named human learning optimization (HLO) is presented in this paper in which the individual learning operator, social learning operator, random exploration learning operator and re-learning operator are developed to generate new solutions and search for the optima by mimicking the human learning process. Then HLO is ...

Added: June 24, 2015