.png){kind=icon}
返回
Scalable and space-efficient Robust Matroid Center algorithms
.png){kind=icon}
OA
AI
DOI：10.1186/s40537-023-00717-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Given a dataset Vof points from some metric space, a popular robust formulation of the k-center clustering problem requires to select k points (centers) of Vwhich minimize the maximum distance of any point of V from its closest center, excluding the z most distant points (outliers) from the computation of the maximum. In this paper, we focus on an important constrained variant of the robust k-center problem, namely, the Robust Matroid Center (RMC) problem, where the set of returned centers are constrained to be an independent set of a matroid of rank k built on V. Instantiat-ing the problem with the partition matroid yields a formulation of the fair k-center problem, which has attracted the interest of the ML community in recent years. In this paper, we target accurate solutions of the RMC problem under general matroids, when confronted with large inputs. Specifically, we devise a coreset-based algorithm afford-ing efficient sequential, distributed (MapReduce) and streaming implementations. For any fixed e > 0 , the algorithm returns solutions featuring a (3 + e)-approximation ratio, which is a mere additive term e away from the 3-approximations achievable by the best known polynomial-time sequential algorithms. Moreover, the algorithm obliviously adapts to the intrinsic complexity of the dataset, captured by its doubling dimension D. For wide ranges of k, z, e, D , our MapReduce/streaming implementations require two rounds/one pass and substantially sublinear local/work ing memory. The theoretical results are complemented by an extensive set of experiments on real-world datasets, which provide clear evidence of the accuracy and efficiency of our algorithms and of their improved performance with respect to previous solutions.
Keyword:
STREAMING ALGORITHMS
MAPREDUCE
OUTLIERS
期刊
IF:
6.4
论文数:
1.5K
被引数:
1.1W
机构
引用论文
分享收藏Abundance and population structure of the blue crab Callinectes sapidus (Decapoda, Portunidae) in Thermaikos Gulf (Methoni Bay), northern Aegean Sea.png)
Crustaceana
CrustaceanaIF0
PREAI
分享收藏Fabrication and characterization of silver core and porous silica shell nanocomposite particles
PREAI
分享收藏
查看更多内容