Volume 19, No 6, 2012, P. 9-22

UDC 519.7
E. Kh. Gimadi, A. A. Kurochkin
Effective algorithm for solving a two-level facility location problem on a tree-like network

Abstract:
A two-level facility location problem on a tree-like network is considered. The transportation cost between each pair of sites is defined as the length of the corresponding path in the network. An exact algorithm for solving the problem with time-complexity equals to $O(nm^3)$ is constructed, where $n$ is the number of consumers and $m$ is the maximum number of facilities at both levels.
Il. 3, bibliogr. 7.

Keywords: 2-level facility location problem, polynomial algorithm, tree-like network.

Gimadi Edward Khairutdinovich ^1,2
Kurochkin Alexander Alexandrovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: gimadi@math.nsc.ru, alkurochkin@ngs.ru