A334211 a(n) = 1 + a(n-1)*(A007018(n-1) + 1), with a(0) = 1.

1, 3, 10, 71, 3054, 5518579, 18009568007498, 191802924939285448393150887, 21754999921504126977590785836876485101156736372842942

Offset: 0

Author

Nikolai Zolotykh, Apr 18 2020

Keywords

• nonn

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.
• 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), 56-73.
• 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.

Extensions

Definition has been replaced by the explicit recurrence in terms of A007018. - N. J. A. Sloane, Sep 14 2020