login
A334211
a(n) = 1 + a(n-1)*(A007018(n-1) + 1), with a(0) = 1.
0
1, 3, 10, 71, 3054, 5518579, 18009568007498, 191802924939285448393150887, 21754999921504126977590785836876485101156736372842942
OFFSET
0,2
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(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.
LINKS
A. Yu. Chirkov, D. V. Gribanov and N. Yu. Zolotykh, On the Proximity of the Optimal Values of the Multi-Dimensional Knapsack Problem with and without the Cardinality Constraint, arXiv:2004.08589 [math.OC], 2020.
R. Kohli, and R. Krishnamurti, A total-value greedy heuristic for the integer knapsack problem, Operations Research Letters, 12 (1992), 65-71.
CROSSREFS
Cf. A007018.
Sequence in context: A208999 A181075 A136507 * A337949 A086846 A277614
KEYWORD
nonn
AUTHOR
Nikolai Zolotykh, Apr 18 2020
EXTENSIONS
Definition has been replaced by the explicit recurrence in terms of A007018. - N. J. A. Sloane, Sep 14 2020
STATUS
approved