Том 18, номер 4, 2011 г., Стр. 49-65
УДК 519.854
Забудский Г. Г., Лагздин А. Ю.
Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях
Аннотация:
Рассматривается квадратичная задача о назначениях с минимаксным критерием в терминах теории графов: необходимо разместить вершины графа в узлы сети таким образом, чтобы максимальная связь между смежными вершинами была минимальной. Предлагаются полиномиальные алгоритмы решения этой задачи на специальных типах сетей.
Ил. 7, библиогр. 13.
Ключевые слова: квадратичная задача о назначениях, задача размещения, минимаксный критерий, полиномиальный алгоритм, граф.
Забудский Геннадий Григорьевич 1
Лагздин Артём Юрьевич 1
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: zabudsky@o_m.oscsbras.ru, art.lagzdin@gmail.com
Статья поступила 31 мая 2010 г.
Исправленный вариант — 20 июня 2011 г.
Литература
[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982. — 416 с.
[2] Демиденко В. М. Обобщение условий сильной разрешимости квадратичной задачи о назначениях с матрицами анти-Монжа и Теплица / / Докл. НАН Беларуси, 2003. - Т. 47, № 2. - С. 15-18.
[3] Забудский Г. Г. О некоторых задачах размещения на графах // Тр. XI Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». — Иркутск: ИСЭ им. Л. А. Мелентьева СО РАН, 1998. — С. 135-138.
[4] Забудский Г. Г., Лагздин А. Ю. Алгоритм решения квадратичной задачи о назначениях с минимаксным критерием на дереве / / Материалы VII Междунар. научно-техн. конф. «Динамика систем, механизмов и машин». - Омск: ОмГТУ, 2009. - Т. 3. - С. 23-27.
[5] Иорданский М. А. О минимаксных нумерациях вершин графа // Межвуз. сб. «Комбинаторно-алгебраические методы в прикладной математике». — Горький: ГГУ им. Лобачевского. — 1986. — С. 60-73.
[6] Метельский Н. Н. Методы локальной оптимизации для задачи размещения двудольных графов / / Журн. вычисл. математики и мат. физи¬ки. - 1984. - Т. 24, № 9. - С. 1428-1432.
[7] Сергеев С. И. Квадратичная задача назначения. I // Автоматика и телемеханика. — 1999. — № 8. — С. 127-147.
[8] Arkin E., Hassin R., Sviridenko M. Approximating the maximum quadratic assignment problem // Inf. Process. Lett. — 2001. — Vol. 77. — P. 13-16.
[9] Burkard R. E., Dell'Amico M., Mortello S. Assignment problems. — Philadelphia: SIAM, 2009. - 402 p.
[10] Burkard R. E., Fincke U. On random quadratic bottleneck assignment problems // Math. Programming. — 1982. — Vol. 23, N 1. — P. 227-232.
[11] Farahani R. Z., Hekmatfar M. Facility location: concepts, models, algorithms and case studies. — Heidelberg: Physica-Verl., 2009. — 543 p.
[12] Haralambides J., Makedon F. Approximation algorithms for the bandwidth minimization problem for a large class of trees // Theory Comput. Syst. - 1997. - Vol. 30, N 1. — P. 67-90.
[13] Steinberg L. The backboard wiring problem: a placement algorythm // SIAM. - 1961. - Vol. 3, N 1. — P. 37-50.
