A Survey of Approximation Algorithms for the Universal Facility Location Problem

Hanyin Xiao, Jiaming Zhang, Zhikang Zhang () and Weidong Li
Additional contact information
Hanyin Xiao: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China
Jiaming Zhang: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China
Zhikang Zhang: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China
Weidong Li: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China

Mathematics, 2025, vol. 13, issue 7, 1-35

Abstract: The facility location problem is a classical combinatorial optimization problem with extensive applications spanning communication technology, economic management, traffic governance, and public services. The facility location problem is to assign a set of clients to a set of facilities such that each client connects to a facility and the total cost (open cost and connection cost) is as low as possible. Among its various models, the uncapacitated facility location (UFL) problem is the most fundamental and widely studied. However, in real-world scenarios, resource constraints often make the UFL problem insufficient, necessitating more generalized models. This investigation primarily focuses on the universal facility location (Uni-FL) problem, a generalized framework encompassing both capacitated facility location problems (with hard and soft capacity constraints) and the UFL problem. Through a systematic analysis, we examine the Uni-FL problem alongside its specialized variants: the hard capacitated facility location (HCFL) problem and soft capacitated facility location (SCFL) problem. A comprehensive survey is conducted of existing approximation algorithms and theoretical results. The relevant results of their important variants are also discussed. In addition, we propose some open questions and future research directions for this problem based on existing research.

Keywords: universal; hard capacity; soft capacity; facility location problem; unsplittable; splittable (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/7/1023/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/7/1023/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:7:p:1023-:d:1617402

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().