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

被引:0
作者
R. M. Kolpakov
M. A. Posypkin
Si Tu Tant Sin
机构
[1] Moscow State University,Dorodnicyn Computing Centre
[2] Russian Academy of Sciences,undefined
[3] Moscow Institute of Electronic Equipment,undefined
来源
Automation and Remote Control | 2017年 / 78卷
关键词
knapsack problem; branch-and-bound method; computational complexity; domination relation;
D O I
暂无
中图分类号
学科分类号
摘要
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
页数:11
相关论文
共 9 条
[1]  
Lazarev A.A. G. A. t C. O.(2007)Asymptotic Estimate on the Complexit yof the Branch-and-Bound Method with Branching by a Fractional Variable for the Knapsack Problem Autom. Remote Control 68 583-592
[2]  
Kolpakov R.M.(2008)A Graphical Realization of the Dynamic ProgrammingMethod for Solving NP-hard Combinatorial Problems Diskret. Anal. Issled. Oper 15 58-81
[3]  
Posypkin M.A.(2009)Upper and Lower Bounds on the Complexity of the Branch-and-Bound Method for the Knapsack Problem Comput. Math. Appl. 58 619-631
[4]  
Lazarev A.A.(2010)Upper Bound on the Number of Branchings for the Subset Sum Problem Diskret. Mat. 22 58-73
[5]  
Werner F.(2013)undefined Mat. Vopr. Kibern. 18 213-226
[6]  
Kolpakov R.M.(undefined)undefined undefined undefined undefined-undefined
[7]  
Posypkin M.A.(undefined)undefined undefined undefined undefined-undefined
[8]  
Posypkin M.A.(undefined)undefined undefined undefined undefined-undefined
[9]  
Kolpakov R.M.(undefined)undefined undefined undefined undefined-undefined