Volume 16, No 5, 2009, P. 318
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, polynomialtime 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
email: ageev@math.nsc.ru, gimadi@math.nsc.ru, alkurochkin@ngs.ru
