|
Эта публикация цитируется в 13 научных статьях (всего в 13 статьях)
Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце
Р. М. Колпаков, М. А. Посыпкин
Аннотация:
Статья посвящена вопросам сложности решения задачи об одномерном булевом ранце методом ветвей и границ. Для рассматриваемой сложности получены две верхние оценки. Выделен частный случай задачи о ранце, когда сложность ее решения полиномиально ограничена размерностью задачи. Получены также верхняя и нижняя оценки сложности решения методом ветвей и границ задачи о сумме подмножеств, являющейся частным случаем задачи о ранце.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05-01-00495a, 06-07-89079a.
Статья поступила: 01.04.2009
Образец цитирования:
Р. М. Колпаков, М. А. Посыпкин, “Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце”, Дискрет. матем., 22:1 (2010), 58–73; Discrete Math. Appl., 20:1 (2010), 95–112
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1084https://doi.org/10.4213/dm1084 https://www.mathnet.ru/rus/dm/v22/i1/p58
|
Статистика просмотров: |
Страница аннотации: | 1571 | PDF полного текста: | 597 | Список литературы: | 91 | Первая страница: | 41 |
|