Geodesic
Polynomial algorithm for the path facility location problem with uniform capacities
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 3-18

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : polynomial-time algorithm. 
@article{DA_2009_16_5_a0,
     author = {A. A. Ageev and E. Kh. Gimadi and A. A. Kurochkin},
     title = {Polynomial algorithm for the path facility location problem with uniform capacities},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--18},
     publisher = {mathdoc},
     volume = {16},
     number = {5},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_5_a0/}
}
TY  - JOUR
AU  - A. A. Ageev
AU  - E. Kh. Gimadi
AU  - A. A. Kurochkin
TI  - Polynomial algorithm for the path facility location problem with uniform capacities
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 3
EP  - 18
VL  - 16
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_5_a0/
LA  - ru
ID  - DA_2009_16_5_a0
ER  - 
%0 Journal Article
%A A. A. Ageev
%A E. Kh. Gimadi
%A A. A. Kurochkin
%T Polynomial algorithm for the path facility location problem with uniform capacities
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 3-18
%V 16
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_5_a0/
%G ru
%F DA_2009_16_5_a0
A. A. Ageev; E. Kh. Gimadi; A. A. Kurochkin. Polynomial algorithm for the path facility location problem with uniform capacities. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 3-18. http://geodesic.mathdoc.fr/item/DA_2009_16_5_a0/