
COMMENTS

The denominator for the infinum of the ratio of the optimal value for the objective functions of the integer knapsack problem with n+1 types of items with the additional restriction that only one type of items is allowed to include in the solution and without it. [Sentence not clear, needs editing.  N. J. A. Sloane, Mar 07 2021] The numerator is A007018(n+1).
The sequence a(n)/A007018(n) decreases monotonically and tends to 0.591355492056890...
The infinum for a(n)/A007018(n) is achieved on the problem maximize Sum_{j=1..n} x_j/A007018(j1), subject to Sum_{j=1..n} x_j/(A007018(j1)+mu_n) <= 1, where 0 <= mu_n < 1 and Sum_{j=1..n} 1/(A007018(j1) + mu_n) = 1. In particular, mu_1 = 1, mu_2 = (sqrt(5)1)/2 =~ 0.61803, mu_3 =~ 0.93923, mu_4 =~ 0.99855. The optimal solution vector to this problem is (1,1,...,1) and the optimal solution value is a(n+1)/A007018(n+1), whereas the approximate solution vectors are (1,0,0,...,0), (0,A007018(1),0,...,0), (0,0,A007018(2),...,0), ..., (0,0,0,...,A007018(n1)) and the corresponding value of the objective function is 1.


LINKS

Table of n, a(n) for n=0..8.
A. Yu. Chirkov, D. V. Gribanov and N. Yu. Zolotykh, On the Proximity of the Optimal Values of the MultiDimensional Knapsack Problem with and without the Cardinality Constraint, arXiv:2004.08589 [math.OC], 2020.
A. Yu. Chirkov and V. N. Shevchenko, On the approximation of an optimal solution of the integer knapsack problem by optimal solutions of the integer knapsack problem with a restriction on the cardinality, Diskretn. Anal. Issled. Oper., Ser. 2, 13 (2) (2006), 5673.
R. Kohli, and R. Krishnamurti, A totalvalue greedy heuristic for the integer knapsack problem, Operations Research Letters, 12 (1992), 6571.
