Том 15, номер 1, 2008 г., Стр. 58-81

УДК 519.8
Р. М. Колпаков, М. А. Посыпкин
Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце

Аннотация:
Изучается сложность решения одномерной булевой задачи о ранце методом ветвей и границ в случае ветвления по дробной переменной. Построено семейство задач, для элементов которого получена рекуррентная формула для сложности. Получена верхняя асимптотическая оценка для сложности задач этого семейства.
Библ. 9.

Р. М. Колпаков ¹
М. А. Посыпкин ¹
1. МГУ, мех.-мат. факультет,
Воробьёвы горы, 119992 Москва, Россия
е-mail: foroman@mail.ru

Статья поступила 15 мая 2007 г.
Исправленный вариант — 10 января 2008 г.