EN|RU

Том 18, номер 3, 2011 г., Стр. 49-64

УДК 519.8
Заозерская Л. А., Колоколов А. А., Гофман Н. Г.
Оценки среднего числа итераций для алгоритмов решения некоторых задач булева программирования

Аннотация:
Построены полиномиальные верхние оценки среднего числа итераций для ряда алгоритмов целочисленного программирования при решении многомерной задачи о рюкзаке с булевыми переменными и задачи об упаковке множества на основе предложенного ранее подхода. Описаны расширения известных классов задач, для которых имеют место подобные оценки.
Табл. 2, библиогр. 19.

Ключевые слова: среднее число итераций, задача о рюкзаке, задача об упаковке множества, отсечение Гомори, алгоритм ветвей и границ, алгоритм перебора L-классов.

Заозерская Лидия Анатольевна 1
Колоколов Александр Александрович 1
Гофман Нина Гельмудовна 1

1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: zaozer@ofim.oscsbras.ru, kolo@ofim.oscsbras.ru, ngofman@mail.ru

Статья поступила 1 июня 2010 г.
Исправленный вариант — 7 октября 2010 г.

 © Институт математики им. С. Л. Соболева, 2015