Э.Х. Гимади. Точный алгоритм решения внешнепланарной задачи размещения с улучшенной временной сложностью ... С. 74-81.

УДК 519.85

MSC: 90B80, 90C10, 90C39, 05C10

DOI: 10.21538/0134-4889-2017-23-3-74-81

Полная версия статьи

Исследования поддержаны Российским научным фондом, грант №16-11-10041.

Рассматривается сетевая задача размещения с неограниченными объемами производства. В общем случае задача $NP$-трудна. Известно, что задача точно решается с квадратичной трудоемкостью на древовидной сети. В статье исследуется случай сети, представляемой внешнепланарным графом, т.е. графом, все вершины которого принадлежат одной (внешней) грани. Для точного решения рассматриваемой задачи был известен алгоритм с временной сложностью $O(n m^3)$, где $n$ - число вершин, $m$ - число возможных мест размещения предприятий. При использовании некоторых свойств внешнепланарных графов (бинарных 2-деревьев) и учете существования оптимального решения с совокупностью центрально связных областей обслуживания получены рекуррентные соотношения, позволяющие построить точный алгоритм, решающий задачу с уменьшенной в $\sqrt{m}$ раз временной сложностью.

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

Список литературы

1. Discrete location theory / eds. P.B. Mirchandani, R.L. Francis. Wiley-Interscience Series in Discrete Mathematics and Optimization. N.Y.; Chichester; Brisbane; Toronto;  Singapour: Wiley and Sons Inc., 1990. 576 p. ISBN: 978-0-471-89233-5.

2. Трубин В.А. Эффективный алгоритм решения задачи размещения на сети в форме дерева // Докл. АН СССР. 1976. T. 231, № 3. C. 547-550.

3. Kolen A. Solving covering problems and the uncapacitated plant location on the trees // Eur. J. Oper. Res. 1983. Vol. 12, no. 3. P. 266-278.

4. Гимади Э.Х. Эффективный алгоритм размещения с областями обслуживания, связными относительно ациклической сети // Управляемые системы: сб. ст. / ИМ СО РАН. Новосибирск, 1983. Вып. 23. C. 12-23.

5. Billionet A., Costa M.-C. Solving the uncapacitated plant location problem on trees // Discrete Appl. Math. 1994. Vol. 49, no. 1-3. P. 51-59.

6. Агеев А.А. Полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сети // Управляемые системы: cб. ст. / ИМ СО РАН. Новосибирск, 1990. Вып. 30. С. 3-16.

7. Гимади Э.Х. Задача размещения на сети с центрально-связными областями обслуживания // Управляемые системы: сб. ст. / ИМ СО РАН. Новосибирск, 1984. Вып. 25. C. 38-47.

8. Valdes J., Tarjan R., Lawler E. The recognition of series parallel digraphs // SIAM J. Comput. 1982. Vol. 11, no. 2. P. 298-313.

9. Агеев А.А. Графы, матрицы и простейшая задача размещения // Управляемые системы: сб. ст. / ИМ СО РАН. Новосибирск, 1989. Вып. 29. С. 3-11. Hassin R., Tamir A. Efficient algorithm for optimization and selection on series-parallel graphs // SIAM J. Algebraic Discrete Methods. 1986. Vol. 7, № 3. P. 379-389.

10.  Hassin R., Tamir A.  Efficient algorithm for optimization and selection on series-parallel graphs // SIAM J. Algebraic Discrete Methods. 1986.
    Vol.~7, no. 3. P. 379-389.

Поступила 16.05.2017

Гимади Эдуард Хайрутдинович
д-р физ.-мат. наук, профессор, главный науч. сотрудник
Институт математики им. С.Л. Соболева CО РАН,
г. Новосибирск
e-mail: gimadi@math.nsc.ru

English

E.Kh. Gimadi. An optimal algorithm for an outerplanar facility location problem with improved time complexity.

We consider a network facility location problem with unbounded production levels. This problem is NP-hard in the general case and is known to have an optimal solution with quadratic complexity on a tree network. We study the case of a network representable by an outerplanar graph, i.e., by a graph whose vertices belong to one (outer) face. This problem is known to have an optimal algorithm with time complexity $O(nm^3)$, where $n$ is the number of vertices and $m$ is the number of possible facility locations. Using some properties of outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally connected service domains, we obtain recurrence relations for the construction of an optimal algorithm with time complexity that is smaller by a factor of$\sqrt{m}$ than the time complexity of the earlier algorithm.

Keywords: facility location problem, network, outerplanar graph, optimal algorithm, time complexity, connectedness.

 The paper was received by the Editorial Office on May 16, 2017.

Eduard Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090  Russia, e-mail: gimadi@math.nsc.ru .