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

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 1
Gimadi Edward Khairutdinovich 1

Kurochkin Alexandr Alexandrovich 1
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

 © Sobolev Institute of Mathematics, 2015