Publication:
On using gray codes to improve the efficiency of the parallel exhaustive search algorithm for the knapsack problem

Простая страница элемента
dc.contributor.authorNatalia, K.
dc.contributor.authorMikhail, K.
dc.contributor.authorGeorgii, B.
dc.contributor.authorКуприяшин, Михаил Андреевич
dc.contributor.authorБорзунов, Георгий Иванович
dc.date.accessioned2024-11-20T10:34:57Z
dc.date.available2024-11-20T10:34:57Z
dc.date.issued2019
dc.description.abstract© 2019 IEEE In previous papers, we stated that splitting the lexicographic sequence into equal parts does not yield uniform workload distribution for a parallel computational system. One of the options we have considered is breaking the packing vectors space into classes based on the vectors' Hamming weight, and then split each of the classes into equal parts. In this paper, we investigate another load balancing technique based on using the Gray codes instead of the lexicographic sequence. As only one element of the packing changes on every step, we can calculate the packing weight dynamically. Thus, the time needed to weigh a packing becomes both shorter and more uniform. We study the properties of the Gray codes and analyze their impact on the algorithm run time and efficiency of parallel computation.
dc.format.extentС. 1821-1825
dc.identifier.citationNatalia, K. On using gray codes to improve the efficiency of the parallel exhaustive search algorithm for the knapsack problem / Natalia, K., Mikhail, K., Georgii, B. // Proceedings of the 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElConRus 2019. - 2019. - P. 1821-1825. - 10.1109/EIConRus.2019.8657131
dc.identifier.doi10.1109/EIConRus.2019.8657131
dc.identifier.urihttps://www.doi.org/10.1109/EIConRus.2019.8657131
dc.identifier.urihttps://www.scopus.com/record/display.uri?eid=2-s2.0-85063533023&origin=resultslist
dc.identifier.urihttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000469452600424
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/16752
dc.relation.ispartofProceedings of the 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElConRus 2019
dc.titleOn using gray codes to improve the efficiency of the parallel exhaustive 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
Файлы
Коллекции
Публикации