Geodesic
Capacitated facility location problem on random input data
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 23-39

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

The Capacitated Facility Location Problem (CLFP) on random input data is considered. It is assumed that the transportation costs take random values according to discrete uniform distribution on the integer segment $[1,r]$. For CFLP with uniform capacity restrictions an algorithm with time complexity $O(n\log m)$ is constructed and conditions of asymptotical optimality are established (where $n$ is the number of consumers and $m$ is the number of facilities). For CFLP with various capacities an algorithm with time complexity $O(n^{2(1-\theta)}m)$ is given and the conditions of asymptotical optimality for some $\theta\frac12$ are established. Ill. 1, bibliogr. 17.
Keywords: facility location problem, probability, asymptotical optimality.
Mots-clés : polynomial algorithm 
@article{DA_2014_21_5_a2,
     author = {A. A. Kurochkin},
     title = {Capacitated facility location problem on random input data},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {23--39},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_5_a2/}
}
TY  - JOUR
AU  - A. A. Kurochkin
TI  - Capacitated facility location problem on random input data
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 23
EP  - 39
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_5_a2/
LA  - ru
ID  - DA_2014_21_5_a2
ER  - 
%0 Journal Article
%A A. A. Kurochkin
%T Capacitated facility location problem on random input data
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 23-39
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_5_a2/
%G ru
%F DA_2014_21_5_a2
A. A. Kurochkin. Capacitated facility location problem on random input data. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 23-39. http://geodesic.mathdoc.fr/item/DA_2014_21_5_a2/