О наилучшем выборе переменной ветвления в задаче о сумме подмножеств

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