|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранцестатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Колпаков Р.М., Посыпкин М.А.
- Журнал: Дискретная математика
- Том: 22
- Номер: 1
- Год издания: 2010
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 58
- Последняя страница: 73
- Аннотация: Статья посвящена вопросам сложности решения задачи об одномерном булевом ранце методом ветвей и границ. Для рассматриваемой сложности получены две верхние оценки. Выделен частный случай задачи о ранце, когда сложность ее решения полиномиально ограничена размерностью задачи. Получены также верхняя и нижняя оценки сложности решения методом ветвей и границ задачи о сумме подмножеств, являющейся частным случаем задачи о ранце.
- Добавил в систему: Колпаков Роман Максимович