Exact and greedy solutions of the knapsack problem: the ratio of values of objective functions |
| |
Authors: | A. A. Korbut I. Kh. Sigal |
| |
Affiliation: | 1.Institute for Economics and Mathematics,Russian Academy of Sciences,St. Petersburg,Russia;2.Computing Center,Russian Academy of Sciences,Moscow,Russia |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|