Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце

Статья посвящена вопросам сложности решения задачи об одномерном булевом ранце методом ветвей и границ. Для рассматриваемой сложности получены две верхние оценки. Выделен частный случай задачи о ранце, когда сложность ее решения полиномиально ограничена размерностью задачи. Получены также верхняя и нижняя оценки сложности решения методом ветвей и границ задачи о сумме подмножеств, являющейся частным случаем задачи о ранце.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05-01-00495a, 06-07-89079a.