6 papers
Coresets for -Means: When Does Uniform Sampling Suffice?
Amir Carmel, Robert Krauthgamer
Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets. We study uniform sampling, which is an extremely simple and ul…
Recovery Beats Storage: Improved Space for Preprocessed 3SUM
Amir Carmel, Yakov Kosoburd, Robert Krauthgamer
The 3SUM problem asks, given sets of integers, whether there exist and whose sum belongs to . In the preprocessed variant with unknown , one preproc…
Optimal Stable Coresets for Geometric Median via Uniform Sampling
Amir Carmel, Robert Krauthgamer, Nir Petruschka
The geometric median problem asks to find a point in that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geomet…
A Scalable and Unified Framework to Weighted Rank Aggregation
Amir Carmel, Debarati Das, Tien-Long Nguyen
The rank aggregation problem seeks to combine multiple rank orderings of the same set of candidates into a single consensus ordering. Such problems arise in diverse domains, includ…
Stable coresets: Unleashing the power of uniform sampling
Amir Carmel, Robert Krauthgamer
Uniform sampling is a highly efficient method for data summarization. However, its effectiveness in producing coresets for clustering problems is not yet well understood, primarily…
Fitting Tree Metrics and Ultrametrics in Data Streams
Amir Carmel, Debarati Das, Evangelos Kipouridis +1
Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Given a posi…