On the best choice of a branching variable in the subset sum problemстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 6 декабря 2018 г.
Аннотация:The paper is concerned with estimating the computational complexity of the branch-and-bound method for the subset sum problem. We study the relationship between the way of decomposition of subproblems and the number of the method steps. The standard variant of the branch-and-bound method for the subset sum problem with binary branching is considered: any subproblem is decomposed into two more simple subproblems by assigning values 0 and 1 to a selected branching variable. It is shown that for any set of parameters of the problem the procedure of branching variables selection in the descending order of their weights is optimal.