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

Простая страница элемента
dc.contributor.authorSlonkina, I.
dc.contributor.authorKupriyashin, M.
dc.contributor.authorBorzunov, G.
dc.contributor.authorКуприяшин, Михаил Андреевич
dc.contributor.authorБорзунов, Георгий Иванович
dc.date.accessioned2024-11-20T10:32:01Z
dc.date.available2024-11-20T10:32:01Z
dc.date.issued2019
dc.description.abstract© 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.
dc.format.extentС. 1811-1815
dc.identifier.citationSlonkina, 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
dc.identifier.doi10.1109/EIConRus.2019.8657309
dc.identifier.urihttps://www.doi.org/10.1109/EIConRus.2019.8657309
dc.identifier.urihttps://www.scopus.com/record/display.uri?eid=2-s2.0-85063502646&origin=resultslist
dc.identifier.urihttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000469452600422
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/16735
dc.relation.ispartofProceedings of the 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElConRus 2019
dc.titleAnalysis and optimization of the packing tree search algorithm for the knapsack problem
dc.typeConference Paper
dspace.entity.typePublication
relation.isAuthorOfPublicationd121410c-d598-45ff-aa9f-b1be65adf4c5
relation.isAuthorOfPublication8c9c0f28-77ec-4d14-9c70-e751d6c044c6
relation.isAuthorOfPublication.latestForDiscoveryd121410c-d598-45ff-aa9f-b1be65adf4c5
relation.isOrgUnitOfPublication010157d0-1f75-46b2-ab5b-712e3424b4f5
relation.isOrgUnitOfPublication.latestForDiscovery010157d0-1f75-46b2-ab5b-712e3424b4f5
Файлы
Коллекции
Публикации