A primal-dual polynomial approximation algorithm for the uncapacitated facility location problem

The Uncapacitated Facility Location Problem is a well-known discrete optimization problem. We consider a problem with unsplittable demands and without triangle inequality. These problem is NP-hard in the strong sense. We propose a primal-dual approximate polynomial algorithm with a posteriori performance guarantee. The approach comprises two polynomial approximation algorithms: $\mathcal A_1$, which utilises the greedy heuristic, and $\mathcal A_2$, as proposed by the authors, based on identifying the dead-end solution to the dual problem. The complexity of the proposed algorithm is $\mathcal O(mn(m + \log n))$, where $m$ is the number of facilities and $n$ is the number of customers. In the dual algorithm, a binary heap is used, which significantly reduced the actual runtime of the algorithm. The reduction in runtime was especially noticeable on multidimensional examples. Numerical experiments with randomly generated instances demonstrate the effectiveness of the proposed algorithms through their computational results.