Capacitated facility location problem on random input data

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.