Publication: Statistical Analysis of Binary Vector Enumeration Methods in Combinatorial Optimization
Дата
2020
Авторы
Kupriyashina, N. A.
Kupriyashin, M. A.
Slonkina, I. S.
Borzunov, G. I.
Journal Title
Journal ISSN
Volume Title
Издатель
Аннотация
© 2020 IEEE.In this paper, we review and analyze the efficiency of several binary vector enumeration algorithms we have been using in our work on the Knapsack Problem. As we keep in mind the possibility of massively parallel computation, we are interested in algorithms that are able to start the search from any vector (identified by ordinal number). In this case, it is possible to implement static load balancing efficiently. Apart from the actual implementation performance, we study the load balancing diagrams for each of the algorithms. We assume that every bit of the binary vector is associated with some fixed amount of work a computer must do and examine the resulting complexity of subtasks obtained by splitting the vector sequences into subsequences.
Описание
Ключевые слова
Цитирование
Statistical Analysis of Binary Vector Enumeration Methods in Combinatorial Optimization / Kupriyashina, N.A. [et al.] // Proceedings of the 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, EIConRus 2020. - 2020. - P. 2084-2089. - 10.1109/EIConRus49466.2020.9039096