Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

№18, Москва, 2013
Авторы: Колпаков Р.М., Посыпкин М.А.
Верхняя оценка числа ветвлений для задачи о сумме подмножеств
Аннотация:
В работе получена верхняя оценка сложности решения задачи о сумме подмножеств методом ветвей и границ с ветвлением по переменной с максимальным весом. Эта оценка зависит только от исходных данных задачи, тем самым позволяя определять максимальное необходимое для решения задачи число операций до начала решения задачи на основании ее исходных данных.
Ключевые слова:
задачи о ранце, метод ветвей и границ, вычислительная сложность
Язык публикации: русский, страниц: 14 (с. 213-226)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Колпаков Роман Максимович,  ,  механико-математический ф-т МГУ им. М.В.Ломоносова
  • Посыпкин Михаил Анатольевич,  Институт проблем передачи информации им. А.А. Харкевича РАН