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.
Keywords: Facility Location Problem, NP-hard problem, approximation algorithm, algorithm with a posteriori performance guarantee, primal-dual algorithm, binary heap
Received April 23, 2025
Revised July 18, 2025
Accepted July 21, 2025
Funding Agency: The work was supported under state contract IM SB RAS no. FWNF-2022-0019.
Edward Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gimadi@math.nsc.ru
Evgenii Nikolaevich Goncharov, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gon@math.nsc.ru
Alexandr Alexandrovich Shtepa†, e-mail: gimadi@math.nsc.ru
REFERENCES
1. Jiaa H., Ordocez F., Dessouky M. A modeling framework for facility location of medical services for large-scale emergencies. IIE Transactions, 2007, vol. 39, no. 1, pp. 41–55. https://doi.org/10.1080/07408170500539113
2. Frank C., Römer K. Distributed facility location algorithms for flexible configuration of wireless sensor networks. In: Proc. Third IEEE Inter. Conf. “Distributed computing in sensor systems” (DCOSS 2007). Berlin, Heidelberg, Springer, 2007, vol. 4549, pp. 124–141. https://doi.org/10.1007/978-3-540-73090-3_9
3. Frey B.J., Dueck D. Clustering by passing messages between data points. ,Science 2007, vol. 315, no. 5814, pp. 972–976. https://doi.org/10.1126/science.1136800
4. Wang Q., Batta R., Rump C.M. Facility location models for immobile servers with stochastic demand. Naval Research Logistics, 2004, vol. 51, no. 1, pp. 137–152. https://doi.org/10.1002/nav.10110
5. Klose A., Drexl A. Facility location models for distribution system design. Eur. J. Operat. Research, 2005, vol. 162, no. 1, pp. 4–29. https://doi.org/10.1016/j.ejor.2003.10.031
6. Ulukan Z., Demircioğlu E. A survey of discrete facility location problems. Inter. J. Industrial and Manufacturing Engineering, 2015, vol. 9, no. 7, pp. 2487–2492. https://doi.org/10.5281/zenodo.1108652
7. Sevaux M., Sörensen K., Pillay N. Adaptive and multilevel metaheuristics. In: Handbook of heuristics R. Marti, P. Pardalos, M. Resende (eds.) Cham: Springer Inter. Publ., 2018, pp. 3–21.
8. Cornuéjols G., Nemhauser G.L., Wolsey L.A. The uncapacitated facility location problem. In: Discrete Location Theory. P. Mirchandani, R. Francis (eds.) NY, John Wiley and Sons, 1990, pp. 119–171.
9. Vazirani V. Approximation algorithms. Berlin, Heidelberg, Springer, 2001, 378 p. ISBN: 3540653678 .
10. Hansen P., Brimberg J., Urosevic D., Mladenovic N. Primal-dual variable neighborhood search for the simple plant-location problem. INFORMS J. Comput., 2007, vol. 19, no. 4, pp. 552–564. https://doi.org/10.1287/ijoc.1060.0196
11. Dinur I., Steurer D. Analytical approach to parallel repetition. In: Proc. of the forty-sixth annual ACM symposium on Theory of computing (STOC’14), NY, 2014, pp. 624–633. https://doi.org/10.1145/2591796.2591884
12. Gimadi E.Kh., Glebov N.I., Dement’ev V.T. On a method of constructing a lower estimate and an approximate solution with an aposteriori exactness estimation for a standardization problem. Upravlyayemyye sistemy, 1974, vol. 13, pp. 26–31 (in Russian).
13. Beresnev V.L., Gimadi E.Kh., Dementyev V.T. Ekstremal’nyye zadachi standartizatsii [Extremal problems of standardization]. Novosibirsk, Nauka, 1978, 333 p.
14. Kleinberg D., Tardos É. Algorithm Design. Boston, NY, Addison Wesley/Pearson, 2006, 864 p. ISBN: 0-321-29535-8 . Translated to Russian under the title Razrabotka i primeneniye, St. Petersburg, Piter Publ., 2016, 800 p. ISBN: 978-5-496-01545-5 .
15. Sonuc E., Özcan E. An adaptive parallel evolutionary algorithm for solving the uncapacitated facility location problem. Expert Syst. Appl., 2023, vol. 224, art. 119956. https://doi.org/10.1016/j.eswa.2023.119956
Cite this article as: E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A primal-dual polynomial approximation algorithm for the uncapacitated facility location problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 77–90.
