Реферат: 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.

Библиографическая ссылка: 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

Оригинальная: Гимади Э.Х. , Гончаров Е.Н. , Штепа А.А.
Прямо-двойственный полиномиальный приближенный алгоритм для задачи размещения предприятий
Труды Института математики и механики УрО РАН (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

Даты:

Поступила в редакцию:	23 апр. 2025 г.
Принята к публикации:	21 июл. 2025 г.
Опубликована в печати:	5 июн. 2026 г.
Опубликована online:	5 июн. 2026 г.

Идентификаторы БД:

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

Альметрики: