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

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