О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ

Исследуется параллельная сложность решения задач оптимизации методом ветвей и границ. Рассматривается стандартная схема реализации метода ветвей и границ на параллельной системе, при которой вначале работает только один из процессоров, после чего полученные подзадачи передаются для обработки другим процессорам. Для этой схемы найдена нижняя оценка параллельной сложности, независящая от задачи. Изучается сложность рассматриваемой схемы для задачи о булевом ранце. Для классического алгоритмически трудного примера получены оценки параллельной сложности и показано, что эти оценки совпадают по порядку между собой и с общей нижней оценкой параллельной сложности. Тем самым показано, что общая нижняя оценка достигается по порядку для некоторых оптимизационных задач.

Статья представлена к публикации членом редколлегии: А. А. Лазарев