Volume 21, No 5, 2014, P. 23-39

UDC 519.8
A. A. Kurochkin
Capacitated facility location problem on random input data

Abstract:
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., bibliogr. 17.

Keywords: facility location problem, polynomial algorithm, probability, asymptotical optimality.

Kurochkin Alexander Alexandrovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: alkurochkin@ngs.ru