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 Кибербезопасность IT Congress 2024
ISSN: 2307-8162