Uniform Capacitated Facility Location Problem with Random Input Data

The Capacitated Facility Location Problem with uniform capacitates and some specific demand restrictions is studied in this paper. Elements of cost matrix $(g_{ij})$ are assumed to take random values according to discrete uniform distribution. An approximation algorithm for solving this problem is suggested and the probabilistic analysis of its work is demonstrated. A key role in this algorithm belongs to the procedure of finding the perfect matching in graph with random edges. The conditions when the algorithm is asymptotically exact with time complexity $O(n \ln m)$ ($n$ — the number of clients, $m$ — the number of facilities) are found.