EN|RU 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 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