The facility location problem with maximum distance constraint

Motivated by practical problems, we investigate the facility location problem with maximum distance constraint, which requires that the distance from each customer to open facilities must not exceed a given threshold value of L. The goal is to minimise the sum of the opening costs of the facilities. We show that this problem is NP-hard and analyse its lower bound. As no (alpha, 1)-approximation algorithm with alpha < 3 exists, we provide a (3,1)-approximation algorithm that violates the maximum distance constraint. Based on this algorithm, we propose a 3-approximation algorithm for the k-supplier problem. The difference between this algorithm and the previous one in [12] is that the proposed algorithm avoids the construction of many bottleneck graphs, making the proposed algorithm less demanding in terms of memory and more suitable for large-scale problems. (c) 2023 Elsevier B.V. All rights reserved.

Automated summary

The facility location problem with maximum distance constraint is investigated and a (3,1)-approximation algorithm is proposed. The algorithm is compared with the previous one and is found to have lower memory requirements and is suitable for large-scale problems.