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

Abstract

Ratios δ 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 δ with the ratio Δ 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 δ and Δ were obtained. A computational experiment was conducted to investigate the ratio of δ of problems of one- and two-dimensional knapsack problems with Boolean variables. A hypothesis on asymptotic behavior of the ratio δ with growth of the number of problem variables was formulated.