Amir Carmel

Amir Carmel, Robert Krauthgamer, Nir Petruschka

The geometric median problem asks to find a point in $\mathbb{R}^d$ that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geometry and appears as a subroutine in numerous optimization tasks, many of which require the solution to satisfy additional structural constraints. A common approach to reduce the input size is to construct a coreset, which is a small weighted subset that faithfully represents the input for a specific optimization problem. Strong coresets preserve the cost of every candidate solution but require linear time to construct; weak coresets admit sublinear construction, in fact by uniform sampling, but only preserve near-optimal solutions, which is insufficient when the solution is constrained. To address this, we focus instead on the recently introduced intermediate notion of a \emph{stable coreset}, which simultaneously handles all constrained variants. Currently, there is a large gap between the known sample sizes for stable and weak coresets. Our main result is that a uniform sample of size $O(ε^{-2} \log \tfrac{1}ε)$ is a stable $(ε, O(ε))$-coreset for the geometric median, with high constant probability, and this bound is tight up to the logarithmic factor. Our analysis adapts recent machinery of Carmel and Krauthgamer (ICLR 2026) for constructing stable coresets, which incurs an $O(\log d)$ factor. We show an iterative argument that progressively reduces the sample size, and eliminates this dependence on the dimension $d$. At a high level, this approach resembles the technique of iterative size reduction, which is applicable for strong coresets but not for weak coresets.

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, including web search, employment, college admissions, and voting. In this work we focus on the 1-median objective: given a set of m rankings over [n], the goal is to compute a ranking that minimizes the sum of its distances to all input rankings. We study rank aggregation under several classical distance metrics: Ulam distance, Spearman's footrule, Hamming distance, and Kendall-tau, as well as their weighted variants. Our contributions begin with a novel unified framework that identifies a key structural property: it suffices to focus on a small subset of rankings, where the corresponding local one-median provides a good approximation to the global median. This principle extends across these distance measures, yielding a general algorithmic framework for weighted rank aggregation. Building on this, we present a new approximation algorithm for rank aggregation under the Ulam distance that scales in the Massively Parallel Computation (MPC) model. Our algorithm computes a $(2-α)$-approximation, for a constant $α>0$, to the 1-median in a constant number of rounds, using local memory sublinear in n and total memory near-linear in n. We further design new MPC approximation algorithms for Spearman's footrule and for the element-weighted variants of Hamming and Kendall-tau distances. For each metric, we obtain a $(2-ζ)$-approximation, for a constant $ζ>0$, to the 1-median in a constant number of rounds, using local memory sublinear in n and total memory linear or near-linear in n. Moreover, for the Ulam distance, we simplify and strengthen the analysis of Chakraborty et al., obtaining an improved 1.968-approximation that further extends to the weighted setting.