KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №18, Moscow, 2013
Authors: Kolpakov R.M., Posypkin M. A.
Upper bound on the number of branchings for the subset sum problem
Abstract:
In the paper un upper bound for the complexity of solving the subset sum problem by the Branch-and-Bound method with the decomposition along the free variable with the maximal weight is obtained. This bound can be easily derived from the input data of the problem. So this bound allows to preliminarily estimate the computational resources required for solving the subset sum problem by the Branch-and-Bound method.
Keywords:
knapsack problems, Branch-and-Bound method; computational complexity
Publication language: russian,  pages: 14 (p. 213-226)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTex