Improvements on the k-center Problem for Uncertain Data

Summary: Reduces uncertain k-center to k-center on carefully chosen deterministic representatives, yielding simple, fast algorithms. Improves guarantees to 10-approximation in arbitrary metrics and (3+ε)-approximation in Euclidean space, with streaming/big-data applicability. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 1748
Venue: PODS
Year: 2018
Pagerank: 5.3766157e-05
Overall Rank: 8,741 | 40.03%
DOI: 10.1145/3196959.3196969

Incoming Non-self Citations Over Time

Authors

1. Sharareh Alipour (Institute for Research in Fundamental Sciences)
2. Amir Jafari (Institute for Research in Fundamental Sciences; Sharif University of Technology)

BibTeX Citation

@inproceedings{alipour_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Improvements on the k-center Problem for Uncertain Data}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196969},
        doi = {10.1145/3196959.3196969},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Alipour, Sharareh and Jafari, Amir},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	8.8664016e-05
6,812	Exceeding Expectations and Clustering Uncertain Data	2009	PODS	5.7657129e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,345	Clustering Uncertain Graphs	2018	VLDB
2	9,575	Local Search Methods for k-Means with Outliers	2017	VLDB
3	5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS
4	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
5	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
6	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
7	4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB
8	6,812	Exceeding Expectations and Clustering Uncertain Data	2009	PODS
9	6,974	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB
10	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS