|
Avtomatika i Telemekhanika, 2017, Issue 3, Pages 96–110
(Mi at14415)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
System Analysis and Operations Research
Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering
R. M. Kolpakovab, M. A. Posypkinb, Si Tu Tant Sinc a Moscow State University, Moscow, Russia
b Dorodnicyn Computing Centre, Russian Academy of Sciences, Moscow, Russia
c Moscow Institute of Electronic Equipment, Moscow, Russia
Abstract:
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.
Keywords:
knapsack problem, branch-and-bound method, computational complexity, domination relation.
Citation:
R. M. Kolpakov, M. A. Posypkin, Si Tu Tant Sin, “Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering”, Avtomat. i Telemekh., 2017, no. 3, 96–110; Autom. Remote Control, 78:3 (2017), 463–474
Linking options:
https://www.mathnet.ru/eng/at14415 https://www.mathnet.ru/eng/at/y2017/i3/p96
|
Statistics & downloads: |
Abstract page: | 240 | Full-text PDF : | 113 | References: | 36 | First page: | 16 |
|