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

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 


1.   P. B. Mirchandani, R. L. Francis (eds). Discrete location theory. 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.   Trubin V.A. An effective algorithm for solving the distribution problem in a network in the form of a tree. Dokl. AN SSSR (Soviet Math. Dokl.), 1976, vol. 231, no. 3, pp. 547–550 (in Russian).

3.   Kolen A. Solving covering problems and the uncapacitated plant location on the trees. Eur. J. Oper. Res., 1983, vol. 12, no. 3, pp. 266–278.

4.   Gimadi E. Kh. Effektivnyi algoritm razmeshcheniya s oblastyami obsluzhivaniya, svyaznymi otnositel’no atsiklicheskoi seti. Upravlyaemye sistemy: sbornik statei Instituta matematiki SO RAN, Novosibirsk, 1983, no. 23, pp. 12–23 (in Russian).

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

6.   Ageev A.A. Polinomial’nyi algoritm resheniya zadachi razmeshcheniya na posledovatel’no-parallel’noi seti. Upravlyaemye sistemy: sbornik statei Instituta matematiki SO RAN, Novosibirsk, 1990, no. 30, pp. 3–16 (in Russian).

7.   Gimadi E. Kh. Zadacha razmeshcheniya na seti s tsentral’no-svyaznymi oblastyami obsluzhivaniya. Upravlyaemye sistemy: sbornik statei Instituta matematiki SO RAN, Novosibirsk, 1984, no. 25, pp. 38–47 (in Russian).

8.   Valdes J., Tarjan R., Lawler E. The recognition of series parallel digraphs. SIAM J. Comput., 1982, vol. 11, no. 2, pp. 298–313.

9.   Ageev A.A. Grafy, matritsy i prosteishaya zadacha razmeshcheniya. Upravlyaemye sistemy: sbornik statei Instituta matematiki SO RAN, Novosibirsk, 1989, no. 29, pp. 3–11 (in Russian).

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. pp. 379–389.