Publication:
Analysis and optimization of the packing tree search algorithm for the knapsack problem

Дата
2019
Авторы
Slonkina, I.
Kupriyashin, M.
Borzunov, G.
Journal Title
Journal ISSN
Volume Title
Издатель
Научные группы
Организационные подразделения
OrgUnit Logo
Организационная единица
Институт интеллектуальных кибернетических систем
Цель ИИКС и стратегия развития - это подготовка кадров, способных противостоять современным угрозам и вызовам, обладающих знаниями и компетенциями в области кибернетики, информационной и финансовой безопасности для решения задач разработки базового программного обеспечения, повышения защищенности критически важных информационных систем и противодействия отмыванию денег, полученных преступным путем, и финансированию терроризма.
Выпуск журнала
Аннотация
© 2019 IEEE The Packing Tree Search algorithm proved to be one of the best exact algorithms for the Knapsack Problem in cryptography: while free from the memory-related limitations of the Horowitz-Sahni list merging algorithm, it still offers a significant performance boost if compared to the Exhaustive Search algorithm. The algorithm also seems to be scalable, albeit the parallel computation efficiency may be as low as 50-60%. In this paper, we consider improvements to the base algorithm to reduce its complexity. In particular, we study the dynamic packing weight calculation, the replacement of stack-based and linearization-based tree traversal techniques with faster step-based traversal routines and substitution of the original problem instance with the conjugate in case it reduces the complexity. In conclusion, we analyze the impact of these improvements on the acceleration and efficiency of parallel computation.
Описание
Ключевые слова
Цитирование
Slonkina, I. Analysis and optimization of the packing tree search algorithm for the knapsack problem / Slonkina, I., Kupriyashin, M., Borzunov, G. // Proceedings of the 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElConRus 2019. - 2019. - P. 1811-1815. - 10.1109/EIConRus.2019.8657309
URI
https://www.doi.org/10.1109/EIConRus.2019.8657309
 https://www.scopus.com/record/display.uri?eid=2-s2.0-85063502646&origin=resultslist
 http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000469452600422
 https://openrepository.mephi.ru/handle/123456789/16735
Коллекции
Публикации