Upper bound for the complexity of one of the variants of the branch and bound method for the subset sum problem

Р.М. Колпаков, М.А. Посыпкин, Си Ту Тант Син

Abstract


In the paper we obtain an upper bound for the complexity of solving the subset sum problem which is a particular case of the knapsack problem by one of the variants of  the branch-and-bound method with an additional pruning rule based on the comparison of  the maximum and minimum number of items that can be put into the knapsack. As auxiliary results, we establish  various combinatorial properties of subproblems processed for solving the subset sum problem by the considered variant of  the branch-and-bound method.


Full Text:

PDF (Russian)

References


Sigal I.H., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie. M.: Fizmatlit, 2003. – 240 s.

Kellerer H., Pfershy U., Pisinger D. Knapsack Problems. Springer Verlag, 546 p., 2004.

Tarannikov Ju.V. Kombinatornye svojstva diskretnyh struktur i prilozhenija k kriptologii, Moskva: Izdatel'stvo MCNMO, 2011, — 152 c..

Kolpakov R. M., Posypkin M. A. Verhnjaja i nizhnjaja ocenki trudoemkosti metoda vetvej i granic dlja zadachi o rance //Diskretnaja matematika. – 2010. – T. 22. – #. 1. – S. 58-73.

Jablonskij S.V. Vvedenie v diskretnuju matematiku. M: Nauka, 2003.

Finkel'shtejn Ju.Ju. Priblizhennye metody i prikladnye zadachi diskretnogoprogrammirovanija. M.: Nauka, 1976

Lazarev A. A. Graficheskij podhod k resheniju zadach kombinatornoj optimizacii //Avtomatika i telemehanika. – 2007. – #. 4. – S. 13-23.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162