Том 10, серия 2, номер 1, 2003 г., Стр. 3-10
УДК 519.854.3
Н. Ю. Золотых
О сложности решения одного класса задач целочисленного линейного программирования
Аннотация:
Рассматривается задача о рюкзаке, в которой множество допустимых значений$M$ вычисляется с использованием оракула, отвечающего на вопрос "$x\in M$ ?". Установлены нижние оценки числа обращений к оракулу. Предлагаемые оценки близки к известным верхним оценкам.
Библиогр. 13.
Золотых Н. Ю. 1
1. Нижегородский государственный университет им. Н. И. Лобачевского,
603950 Нижний Новгород, пр. Гагарина, 23.
е-mail: zny@uic.nnov.ru
Статья поступила 27 марта 2003 г.
