The capacitated K-center problem

被引：96

作者：

Khuller, S ^{[1
]}

Sussmann, YJ

机构：

[1] Univ Maryland, Dept Comp Sci, College Pk, MD 20742 USA

[2] Univ Maryland, UMIACS, College Pk, MD 20742 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2000年 / 13卷 / 03期

关键词：

approximation algorithms; facility location; K-center;

D O I：

10.1137/S0895480197329776

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The capacitated K-center problem is a basic facility location problem, where we are asked to locate K facilities in a graph and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. Moreover, each facility may be assigned at most L vertices. This problem is known to be NP-hard. We give polynomial time approximation algorithms for two different versions of this problem that achieve approximation factors of 5 and 6. We also study some generalizations of this problem.

引用

页码：403 / 418

页数：16

共 50 条

[41] Approximation algorithms for probabilistic k-center clustering
Alipour, Sharareh
20TH IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM 2020), 2020, : 1 - 11
[42] k-Center Clustering with Outliers in Sliding Windows
Pellizzoni, Paolo
Pietracaprina, Andrea
Pucci, Geppino
ALGORITHMS, 2022, 15 (02)
[43] Efficient Parallel Algorithms for k-Center Clustering
McClintock, Jessica
Wirth, Anthony
PROCEEDINGS 45TH INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING - ICPP 2016, 2016, : 133 - 138
[44] The (K, k)-capacitated spanning tree problem
Arkin, Esther M.
Guttmann-Beck, Nili
Hassin, Refael
DISCRETE OPTIMIZATION, 2012, 9 (04) : 258 - 266
[45] Dimensionality-adaptive k-center in sliding windows
Pellizzoni, Paolo
Pietracaprina, Andrea
Pucci, Geppino
2020 IEEE 7TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA 2020), 2020, : 197 - 206
[46] Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
MeCutchen, Richard Matthew
Khuller, Samir
APPROXIMATION RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, PROCEEDINGS, 2008, 5171 : 165 - 178
[47] One-Dimensional k-Center on Uncertain Data
Wang, Haitao
Zhang, Jingru
COMPUTING AND COMBINATORICS, COCOON 2014, 2014, 8591 : 104 - 115
[48] Approximation algorithms for the individually fair k-center with outliers
Han, Lu
Xu, Dachuan
Xu, Yicheng
Yang, Ping
JOURNAL OF GLOBAL OPTIMIZATION, 2023, 87 (2-4) : 603 - 618
[49] AN ADAPTIVE PROBABILISTIC ALGORITHM FOR ONLINE k-CENTER CLUSTERING
Yang, Ruiqi
Xu, Dachuan
Xu, Yicheng
Zhang, Dongmei
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2019, 15 (02) : 565 - 576
[50] Red-Blue k-Center Clustering with Distance Constraints
Eskandari, Marzieh
Khare, Bhavika B.
Kumar, Nirman
Bigham, Bahram Sadeghi
MATHEMATICS, 2023, 11 (03)

← 1 2 3 4 5 →