Том 21, номер 3, 2014 г., Стр. 64–75

УДК 519.863
Панюков А. В., Шангин Р. Э.
Точный алгоритм решения дискретной задачи Вебера для k-дерева

Аннотация:
Рассматривается известная NP-трудная задача размещения взаимосвязанных объектов — дискретная задача Вебера. Предлагается последовательный детерминированный алгоритм, находящий точное решение задачи для k-дерева и конечного множества позиций размещения. Алгоритм использует идею динамического программирования на основе дерева декомпозиции. Проведён вычислительный эксперимент по анализу эффективности предложенного алгоритма в сравнении с пакетом IBM ILOG CPLEX.
Ил. 2, библиогр. 23.

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

Панюков Анатолий Васильевич ¹
Шангин Роман Эдуардович ¹
1. Южно-Уральский гос. университет,
пр. Ленина, 76, 454080 Челябинск, Россия
е-mail: a_panyukov@mail.ru, shanginre@gmail.com

Статья поступила 3 сентября 2013 г.
Исправленный вариант — 31 января 2014 г.

Литература

[1] Быкова В. В. Вычислительные аспекты древовидной ширины графа // Прикл. дискрет. математика. - 2011. - №3. - С. 65–79.

[2] Быкова В. В. FTP-алгоритмы на графах ограниченной древовидной ширины // Прикл. дискрет. математика. - 2012. - №2. - С. 65–78.

[3] Забудский Г. Г., Лагздин А. Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №4. - С. 49–65.

[4] Забудский Г. Г., Лагздин А. Ю. Динамическое программирование для решения квадратичной задачи о назначениях на дереве // Автоматика и телемеханика. - 2012. - №2. - С. 141–155.

[5] Забудский Г. Г., Филимонов Д. В. О минимакской и минисуммной задачах размещения на сетях // Тр. XII Байкальской междунар. конф. «Методы оптимизации и их приложения» (Иркутск, 24 июня–1 июля
2001 г.). - Иркутск: Изд-во ИГУ, 2001. - С. 150–155.

[6] Панюков А. В. Модели и методы решения задач построения и идентификации геометрического размещения: дисс. ... д-ра физ.-мат. наук: 05.13.16. - Челябинск, 1999. - 260 с.

[7] Панюков А. В., Пельцвергер Б. Ф. Оптимальное размещение дерева в конечном множестве // Журн. вычисл. математики и мат. физики. - 1988. - Т. 28. - С. 618–620.

[8] Панюков А. В., Пельцвергер Б. Ф., Шафир А. Ю. Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности // Автоматика и телемеханика. - 1990. - №9. - С. 153–162.

[9] Сергеев С. И. Квадратичная задача о назначениях. I // Автоматика и телемеханика. - 1999. - №8. - С. 127–47.

[10] Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. - 1978. - №6. - С. 67–70.

[11] Филимонов Д. В. Решение дискретной минимаксной задачи размещения на древовидной сети // Мат. ежегод. научн. семинара аспирантов. - Омск: Изд-во Омск. гос. ун-та, 2003. - С. 58–61.

[12] Шангин Р. Э. Исследование эффективности приближенных алгоритмов решения одного частного случая задачи Вебера // Экономика, статистика и информатика. Вестн. УМО. - 2012. - №1. - С. 163–169.

[13] Шангин Р. Э. О некоторых свойствах n-последовательносвязной цепи // Вестн. ЮУрГУ. Сер. Вычисл. математика и информатика. - 2013. - Т. 2, №1. - С. 106–113.

[14] Arnborg S. Efficient algorithms for combinatorial problems with bounded decomposability - a survey // BIT Numerical Math. - 1985. - Vol. 25, N1. - P. 1–23.

[15] Arnborg S., Proskurowski A. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Appl. Math. - 1989. - Vol. 23. - P. 11–24.

[16] Bodlaender H. L. Treewidth: algorithmic techniques and results // Lect. Notes Comput. Sci. - 1997. - Vol. 1295. - P. 19–36.

[17] Ibarra L. The clique-separator graph for chordal graphs // Discrete Appl. Math. - 2009. - Vol. 157, N 8. - P. 1737–1749.

[18] McKee T. A. On the chordality of a graph // J. Graph Theory. - 1993. - Vol. 17. - P. 221–232.

[19] Panyukov A. V., Pelzwerger B. V. Polynomial algorithms to finite Weber problem for a tree network // J. Comput. Appl. Math. - 1991. - Vol. 35. - P. 291–296.

[20] Robertson N., Seymour P. D. Graph minors. II. Algorithmic aspects of treewidth // J. Algorithms. - 1986. - Vol. 7. - P. 309–322.

[21] Rose D. J. Triangulated graphs and the elimination process // J. Math. Anal. Appl. - 1970. - Vol. 32. - P. 597–609.

[22] Rose D. J. On simple characterizations of k-trees // Discrete Math. - 1973. - Vol. 7. - P. 317–322.

[23] Zabudsky G. G., Filimonov D. V. An algorithm for minimax location problem on tree with maximal distances // Proc. II Int. Workshop Discrete Optimization Methods in Production and Logistics (DOM 2004). - Omsk; Irkutsk: ISU Press, 2004. - P. 81–85.