Volume 16, No 5, 2009, P. 3-18

UDC 519.8
A. A. Ageev, E. Kh. Gimadi, А. А. Kurochkin
The facility location problem with uniform capacities on path graphs is considered

Abstract:
The Facility Location Problem with uniform capacities on path graphs is considered. Earlier it was shown by Ageev that this problem can be solved in $O(m^3n^3+m^5n^2)$ time, where $m$ is the number of facilities and $n$ is the number of clients. In the paper the modified algorithm is presented that has reduced infinitesimal order for the time complexity $O(m^4n^2)$.
Ill. 9, bibl. 24.

Keywords: facility location, uniform capacities, path graphs, polynomial-time algorithm.

Ageev Alexandr Alexandrovich ¹
Gimadi Edward Khairutdinovich ¹
Kurochkin Alexandr Alexandrovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: ageev@math.nsc.ru, gimadi@math.nsc.ru, alkurochkin@ngs.ru