Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #19 Mar 07 2021 01:01:07
%S 1,3,10,71,3054,5518579,18009568007498,191802924939285448393150887,
%T 21754999921504126977590785836876485101156736372842942
%N a(n) = 1 + a(n-1)*(A007018(n-1) + 1), with a(0) = 1.
%C 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).
%C The sequence a(n)/A007018(n) decreases monotonically and tends to 0.591355492056890...
%C The infinum for a(n)/A007018(n) is achieved on the problem maximize Sum_{j=1..n} x_j/A007018(j-1), subject to Sum_{j=1..n} x_j/(A007018(j-1)+mu_n) <= 1, where 0 <= mu_n < 1 and Sum_{j=1..n} 1/(A007018(j-1) + 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(n-1)) and the corresponding value of the objective function is 1.
%H A. Yu. Chirkov, D. V. Gribanov and N. Yu. Zolotykh, <a href="https://arxiv.org/abs/2004.08589">On the Proximity of the Optimal Values of the Multi-Dimensional Knapsack Problem with and without the Cardinality Constraint</a>, arXiv:2004.08589 [math.OC], 2020.
%H A. Yu. Chirkov and V. N. Shevchenko, <a href="http://mi.mathnet.ru/eng/da6">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</a>, Diskretn. Anal. Issled. Oper., Ser. 2, 13 (2) (2006), 56-73.
%H R. Kohli, and R. Krishnamurti, <a href="https://doi.org/10.1016/0167-6377(92)90065-B">A total-value greedy heuristic for the integer knapsack problem</a>, Operations Research Letters, 12 (1992), 65-71.
%Y Cf. A007018.
%K nonn
%O 0,2
%A _Nikolai Zolotykh_, Apr 18 2020
%E Definition has been replaced by the explicit recurrence in terms of A007018. - _N. J. A. Sloane_, Sep 14 2020