Abstract: 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 1 , which utilises the greedy heuristic, and 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 O(mn(m + logn)), 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.

Cite: Gimadi E.K. , Goncharov E.N. , Shtepa A.A.
A Primal-Dual Polynomial Approximation Algorithm for the Uncapacitated Facility Location Problem
Proceedings of the Steklov Institute of Mathematics. 2025. V.331. P.S44-S55. DOI: 10.1134/S0081543826600043 WOS Scopus OpenAlex

Original: Гимади Э.Х. , Гончаров Е.Н. , Штепа А.А.
Прямо-двойственный полиномиальный приближенный алгоритм для задачи размещения предприятий
Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN). 2025. Т.31. №3. С.77-90. DOI: 10.21538/0134-4889-2025-31-3-77-90 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Apr 23, 2025
Accepted:	Jul 21, 2025
Published print:	Jun 5, 2026
Published online:	Jun 5, 2026

Identifiers:

≡ Web of science:	WOS:001786279300007
≡ Scopus:	2-s2.0-105041065613
≡ OpenAlex:	W7163646325

Altmetrics: