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.
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
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