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

被引:19
作者
Korbut, A. A. [1 ]
Sigal, I. Kh.
机构
[1] Russian Acad Sci, Inst Econ & Math, St Petersburg 191187, Russia
基金
俄罗斯基础研究基金会;
关键词
Objective Function; Greedy Algorithm; Regularity Condition; Knapsack Problem; System Science International;
D O I
10.1134/S1064230710050102
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:757 / 764
页数:8
相关论文
共 11 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]  
DANTZIG G, 1966, LINEAR PROGRAMMING I
[3]   The average behaviour of greedy algorithms for the knapsack problem: General distributions [J].
Diubin, G ;
Korbut, A .
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2003, 57 (03) :449-479
[4]  
DYUBIN GN, 1999, SIB ZH IND MAT, V2, P68
[5]   Ratios of optimal values of objective functions of the knapsack problem and its linear relaxation [J].
Galim'yanova, N. N. ;
Korbut, A. A. ;
Sigal, I. Kh. .
JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL, 2009, 48 (06) :906-913
[6]  
Kellerer H., 2004, KNAPSACK PROBLEMS, DOI DOI 10.1007/978-3-540-24777-710
[7]  
Khachaturov V. R., 2000, COMBINATORIAL METHOD
[8]  
Khachaturov VR, 1989, MATH METHODS REGIONA
[9]  
SIGAL IK, 2004, COMP SYST SCI, V43, P94
[10]  
SIGAL IK, 2007, INTRO APPL DISCRETE