Exact and greedy solutions of the knapsack problem: the ratio of values of objective functions

Ratios delta of the values of objective functions of optimal Boolean (or integer) to the values of greedy solutions for the knapsack problem are considered. The relationship of the parameter delta with the ratio Delta of the values of objective functions for the optimal solution of linear relaxation to the values of optimal integer solution was found. Two-sided estimates for delta and Delta were obtained. A computational experiment was conducted to investigate the ratio of delta of problems of one- and two-dimensional knapsack problems with Boolean variables. A hypothesis on asymptotic behavior of the ratio delta with growth of the number of problem variables was formulated.