Exact and greedy solutions of the knapsack problem: the ratio of values of objective functions
Authors:
- 21 October 2010
- journal article
- Published by Pleiades Publishing Ltd in Journal of Computer and Systems Sciences International
- Vol. 49 (5) , 757-764
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
This publication has 3 references indexed in Scilit:
- Ratios of optimal values of objective functions of the knapsack problem and its linear relaxationJournal of Computer and Systems Sciences International, 2009
- Knapsack Problems2004
- The average behaviour of greedy algorithms for the knapsack problem: General distributionsMathematical Methods of Operations Research, 2003