Том 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 г.
Литература
[1] Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1977. — 368 c.
[2] Гришухин В. П. О среднем числе итераций алгоритма Балаша // Исследования по дискретной математике. — М.: Наука, 1973. — C. 58–68.
[3] Гэри М., Джонсон М. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 c.
[4] Заозёрская Л. А., Борисенко Д. А., Гофман Н. Г. О числе допустимых решений задачи об упаковке множества // Материалы VII междунар. научно-технической конф. «Динамика систем, механизмов и машин». Т. 3. — Омск.: Издательство ОмГТУ, 2009. — С. 31–35.
[5] Заозёрская Л. А., Колоколов А. А. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Тр. XIV Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». Т. 1. — Иркутск: ИСЭМ СО РАН, 2008. — С. 388–395.
[6] Заозёрская Л. А., Колоколов А. А. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Журн. вычисл. математики и мат. физики. — 2010. – Т. 50, № 2. —
[7] Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. — 1994. — Т. 1, №2. — С. 18–39.
[8] Колоколов А. А., Девятерикова М. В., Заозёрская Л. А. Регулярные разбиения в целочисленном программировании: Учебное пособие. — Омск: Изд-во ОмГУ, 2007. — 60 c.
[9] Кузюрин Н. Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сиб. журн. исслед. операций. — 1994. — Т. 1, №3. — С. 38–48.
[10] Кузюрин Н. Н., Фомин С. А. Эффективные алгоритмы и сложность вычислений. — 2008. — http://discopal.ispras.ru/ru.book-advanced-algorithms.htm.
[11] Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. — 1979. — Т. 244, №5. — С. 1093–1096.
[12] Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974. — 519 c.
[13] Beier R., Vöcking B. Probabilistic analysis of knapsack core algorithms // Proc. 15th Annual Symp. Discrete Algorithms (SODA–2004). — New Orleans: SIAM, 2004. — P. 468–477.
[14] Brown C. A., Purdom P.W. (Jr.) An average time analysis of backtracking // SIAM J. Comput. — 1981. — Vol. 10, N 3. — P. 583–593.
[15] Dinh Dieu P., Cong Thang L., Tuan Hoa L. Average polynomial time complexity of some NP-complete problems // Theoret. Comput. Sci. — 1986. — Vol. 46, N 2. — P. 219–237.
[16] Gurevitch Y., Shelah S. Expected computation time for Hamiltonian path problem // SIAM J. Comput. — 1987. — Vol. 16, N 3. — P. 486–502.
[17] Nemhauser G. L., Wolsey L. A. Integer and combinatorial optimization. Wiley–Intersci. Publ. — New York; Chichester; Weinheim; Brisbane; Singa?pore; Toronto: John Wiley & Sons, Inc., 1999. — 763 p.
[18] Iwama K. CNF satisfiability test by counting and polynomial average time // SIAM J. Comput. — 1989. — Vol. 18, N 2. — P. 385–391.
[19] Smale S. On the average number of steps of the simplex method of linear programming // Math. Programming. — 1983. — Vol. 27, N 3. — P. 241–262.
