О приближении оптимального решения целочисленной задачи о ранце оптимальными решениями целочисленной задачи о ранце с ограничением на мощность

Рассматриваются целочисленная задача о ранце и целочисленная минимизационная задача о ранце. Под $k$-оптимальным значением рассматриваемых задач понимается оптимальное значение соответствующей задачи с ограничением на мощность решения. Вводятся понятия гарантированной точности $k$-оптимального решения целочисленной задачи о ранце $\alpha_{kn}$ и для целочисленной минимизационной задачи о ранце $\beta_{kn}$, равные точной нижней грани отношения $k$-оптимального значения к оптимальному значению.
Получены формулы, позволяющие вычислять значения $\alpha_{1n}$ и $\alpha_{n-1n}$. Указаны задачи, на которых эти значения достигаются. Вычислены значения $\beta_{1n}$ и $\beta_{n-1n}$, которые в отличие от целочисленной задачи о ранце недостижимы на конкретных задачах. Построены соответствующие серии примеров. Для $k=2,\dots,n-2$ доказаны неравенства $(2^{k+1}-2)/(2^{k+1}-1)\geqslant\alpha_{kn}\geqslant(2^n-2^{n-k})/(2^n-1)$ и $1-2^{-k}\geqslant\beta_{kn}\geqslant(1-2^{1-n})\dotsb(1-2^{-k})$. Библ. 8.