Том 19, номер 6, 2012 г., Стр. 9-22

УДК 519.7
Гимади Э. Х., Курочкин А. А.
Эффективный алгоритм решения двухэтапной задачи размещения на древовидной сети

Аннотация:
Рассматривается двухэтапная задача размещения производства на древовидной сети при условии, что затраты на транспортировку единицы продукции из пункта в пункт равны сумме длин рёбер в цепи, соединяющей эти пункты. Предложен алгоритм для точного решения данной задачи с трудоёмкостью $O(nm^3)$, где $n$ – число пунктов спроса конечного продукта, $m$ – ограничение сверху на число возможных пунктов размещения производства каждого этапа.
Ил. 3, библиогр. 7.

Ключевые слова: двухэтапная задача размещения производства, полиномиальный алгоритм, древовидная сеть.

Гимади Эдуард Хайрутдинович ^1,2
Курочкин Александр Александрович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, alkurochkin@ngs.ru

Статья поступила 8 декабря 2011 г.
Исправленный вариант — 22 апреля 2012 г.

Литература

[1] Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978. — 333 с.

[2] Гимади Э. Х. Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи // Дискрет. анализ и исслед. операций. Cep. 1. — 1995. — Т. 2, № 4. — С. 13–31.

[3] Ageev A., Ye Yi., Zhang J. Improved combinatorial approximation algorithms for the $k$-level facility location problem // SIAM J. Discrete Math. — 2004. — Vol. 18, N 1. — P. 207–217.

[4] Gimadi E. Kh. Exact algorithm for some multi-level location problems on a chain and a tree // Oper. Res. Proc. SOR’96 (Braunschweig, Germany, September 3–6, 1996). — Berlin: Springer-Verl., 1997. — P. 72–77.

[5] Discrete location theory // Wiley-Intersci. Ser. Discrete Math. Optimization. — New York; Chichester; Brisbane; Toronto; Singapour: Wiley & Sons Inc., 1990. — 555 p.

[6] Zhang J. Approximating the two-level facility location problem via a quasi-greedy approach // Proc. 15th ACM-SIAM Symp. Discrete Algorithms SODA (New Orleans, Louisiana, USA, January 11–14, 2004). — Philadelphia: SIAM, 2004. — P. 808–817.

[7] Bumb A. F., KernW. A simple dual ascent algorithm for the multilevel facility location problem // 4th Int. Workshop Approximation Algorithms Comb. Optimization. APPROX 2001 (Berkeley, CA, USA, August 18–20,
2001). — London: Springer-Verl., 2001. — P. 55–62. (Lect. Notes Comput. Sci.; Vol. 2129).