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. This 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: A₁ , which utilises the greedy heuristic, and A₂ , as proposed by the authors, based on identifying the dead-end solution to the dual problem. The complexity of the proposed algorithm is 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 reduces the actual runtime of the algorithm. The reduction in runtime is especially noticeable on high-dimensional instances. Numerical experiments with randomly generated instances demonstrate the effectiveness of the proposed algorithms through their computational results.