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

Эта публикация цитируется в 1 статье

Оценки среднего числа итераций для алгоритмов решения некоторых задач булева программирования

Л. А. Заозёрская, А. А. Колоколов, Н. Г. Гофман

Омский филиал Института математики им. С. Л. Соболева СО РАН, Омск, Россия

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

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

УДК: 519.8

Статья поступила: 01.06.2010
Переработанный вариант: 07.10.2010