2019/12/02 by Jarosław Byrka, Byrka, Jarosław, Mateusz Lewandowski +1
Business, Management and Accounting · Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1912.00770
openalex publication_date 2019/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a variant of the uncapacitated facility location problem (UFL),\nwhere connection costs of clients are defined by (client specific) concave\nnondecreasing functions of the connection distance in the underlying metric. A\nspecial case capturing the complexity of this variant is the setting called\nfacility location with penalties where clients may either connect to a facility\nor pay a (client specific) penalty. We show that the best known approximation\nalgorithms for UFL may be adapted to the concave connection cost setting. The\nkey technical contribution is an argument that the JMS algorithm for UFL may be\nadapted to provide the same approximation guarantee for the more general\nconcave connection cost variant. We also study the star inventory routing with\nfacility location (SIRPFL) problem that was recently introduced by Jiao and\nRavi, which asks to jointly optimize the task of clustering of demand points\nwith the later serving of requests within created clusters. We show that the\nproblem may be reduced to the concave connection cost facility location and\nsubstantially improve the approximation ratio for all three variants of SIRPFL.\n