В. Опарин

Priority Branching Trees. Lower bounds for schedule and knapsack problems

Priority Branching Tree (pBT) --- модель вычисления, предназначенная для оценки времени работы бэктрекинга и алгоритмов на основе динамического программирования.
В докладе буду показаны нижние оценки на pBT для задачи о рюкзаке и составлении расписаний.

Alekhnovich, Borodin, Buresh-Oppenheim, Impagliazzo, Magen, Pitassi "Toward a Model for Backtracking and Dynamic Programming"