Ratios of optimal values of objective functions of the knapsack problem and its linear relaxation

被引：4
作者：
Galim'yanova, N. N. [1 ]
Korbut, A. A.
Sigal, I. Kh.
机构：
[1] Russian Acad Sci, Inst Math Econ, St Petersburg 191187, Russia
来源：
JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL | 2009年 / 48卷 / 06期
基金：
俄罗斯基础研究基金会;
关键词：
Greedy Algorithm; Knapsack Problem; System Science International; Boolean Variable; Linear Relaxation;
D O I：
10.1134/S1064230709060070
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The ratios of the values of objective functions for optimal solutions of linear and integer knapsack problems are considered. Estimates for these ratios are obtained. One-dimensional and multi-dimensional knapsack problems with Boolean variables are studied experimentally. For these problems, a hypothesis is formulated on the asymptotic behavior of the ratio as the number of variables grows.
引用
收藏
页码：906 / 913
页数：8
相关论文
共 7 条
[1]   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
[2]  
DIUBIN GN, 1999, SIB ZH IND MAT, V2
[3]  
DIUBIN GN, 2003, EC MATH INVESTIGATIO, V3, P46
[4]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[5]  
Kellerer H., 2004, KNAPSACK PROBLEMS
[6]  
SIGAL IK, 2004, COMP SYST SCI, V43, P94
[7]  
SIGAL IK, 2007, INTRO APPL DISCRETE
1