Volume 19, No 6, 2012, P. 922
UDC 519.7
E. Kh. Gimadi, A. A. Kurochkin
Effective algorithm for solving a twolevel facility location problem on a treelike network
Abstract:
A twolevel facility location problem on a treelike 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 timecomplexity 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: 2level facility location problem, polynomial algorithm, treelike network.
Gimadi Edward Khairutdinovich ^{1,2}
Kurochkin Alexander Alexandrovich ^{1}
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
email: gimadi@math.nsc.ru, alkurochkin@ngs.ru
