.png){kind=icon}
Return
Approximation algorithm for the fault-tolerant knapsack center problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s11590-026-02303-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we mainly investigate the fault-tolerant knapsack center problem and propose a tight 3-approximation algorithm for it. This problem covers several classical variants of the center problem, including the k-center problem, the knapsack center problem and the fault-tolerant k-center problem. In addition, we also provide a (3, 1)-approximation algorithm for the distance-constrained fault-tolerant facility location problem. Our findings generalize the relevant results in Chen et al. (Algorithmica 75:27-52, 2016), Khuller et al. (Theor Comput Sci 242:237-245, 2000), and Li et al. (Inf Process Lett 184:106447, 2024).
Keywords:
Approximation algorithm
Fault tolerant
k-center problem
Knapsack center problem
Facility location problem
Journal
O
IF:
1.1
Papers:
77
Citations:
2.4K
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSaveLP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties
OAAI
OAAIShareSave
ShareSaveShareSave
View more