Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering

被引:2
作者
Kolpakov, R. M. [1 ,2 ]
Posypkin, M. A. [2 ]
Sin, Si Tu Tant [3 ]
机构
[1] Moscow MV Lomonosov State Univ, Moscow, Russia
[2] Russian Acad Sci, Dorodnicyn Comp Ctr, Moscow, Russia
[3] Moscow Inst Elect Equipment, Moscow, Russia
基金
俄罗斯基础研究基金会;
关键词
knapsack problem; branch-and-bound method; computational complexity; domination relation;
D O I
10.1134/S0005117917030079
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We obtain an exact upper bound on the complexity of solving the Subset Sum problem with a variation of the branch-and-bound method of a special form. Complexity is defined as the number of subproblems considered in the process of solving the original problem. Here we reduce the enumeration by using the domination relation. We construct an instance of the Subset Sum problem on which our bound is realized. The resulting bound is asymptotically twice smaller than the exact upper bound on the complexity of solving this problem with a standard version of the branch-and-bound method.
引用
收藏
页码:463 / 474
页数:12
相关论文
共 10 条
[1]  
[Anonymous], 1990, KNAPSACK PROBLEMS
[2]  
[Anonymous], 2004, Knapsack Problems, DOI DOI 10.1007/978-3-540-24777-710
[3]  
Finkel'shtein YuYu, 1976, PRIBLIZHENNYE METODY
[4]  
Grishukhin V.P, 1976, INVESSTIGATIONS DISC, P203
[5]  
Kolpakov R.M., 2008, DISKRET ANAL ISSLED, V1, P58
[6]  
[Колпаков Роман Максимович Kolpakov Roman Maksimovich], 2010, [Дискретная математика, Discrete Mathematics and Applications, Diskretnaya matematika], V22, P58, DOI 10.4213/dm1084
[7]   Graphic approach to combinatorial optimization [J].
Lazarev, A. A. .
AUTOMATION AND REMOTE CONTROL, 2007, 68 (04) :583-592
[8]   A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems [J].
Lazarev, Alexander A. ;
Werner, Frank .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2009, 58 (04) :619-631
[9]  
Posypkin M.A., 2013, MAT VOPR KIBERN, P213
[10]  
Sigal I.Kh., 2007, Introduction to Applied Discrete Programming. Models and Computational Algorithms