TY - GEN
T1 - A PTAS Framework for Clustering Problems in Doubling Metrics
AU - Wu, Di
AU - Xu, Jinhui
AU - Wang, Jianxin
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - Constrained clustering problems have been studied extensively in recent years. In this paper, we focus on a class of constrained k-median problems with general constraints on facilities, denoted as GCF k-CMedian problems. We present a randomized polynomial-time approximation scheme (PTAS) framework based on the split-tree decomposition and dynamic programming process for GCF k-CMedian problems, such as k-median with service installation costs, k-facility location and priority k-median problems in doubling metrics.
AB - Constrained clustering problems have been studied extensively in recent years. In this paper, we focus on a class of constrained k-median problems with general constraints on facilities, denoted as GCF k-CMedian problems. We present a randomized polynomial-time approximation scheme (PTAS) framework based on the split-tree decomposition and dynamic programming process for GCF k-CMedian problems, such as k-median with service installation costs, k-facility location and priority k-median problems in doubling metrics.
KW - Approximation algorithm
KW - k-median
UR - https://www.scopus.com/pages/publications/85180543627
U2 - 10.1007/978-3-031-49190-0_28
DO - 10.1007/978-3-031-49190-0_28
M3 - Conference contribution
AN - SCOPUS:85180543627
SN - 9783031491894
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 384
EP - 397
BT - Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
A2 - Wu, Weili
A2 - Tong, Guangmo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 29th International Computing and Combinatorics Conference, COCOON 2023
Y2 - 15 December 2023 through 17 December 2023
ER -