О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:Исследуется параллельная сложность решения задач оптимизации методом ветвей и границ. Рассматривается стандартная схема реализации метода ветвей и границ на параллельной системе, при которой вначале работает только один из процессоров, после чего полученные подзадачи передаются для обработки другим процессорам. Для этой схемы найдена нижняя оценка параллельной сложности, независящая от задачи. Изучается сложность рассматриваемой схемы для задачи о булевом ранце. Для классического алгоритмически трудного примера получены оценки параллельной сложности и показано, что эти оценки совпадают по порядку между собой и с общей нижней оценкой параллельной сложности. Тем самым показано, что общая нижняя оценка достигается по порядку для некоторых оптимизационных задач.