2026-09-05T11:38:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26438 2026-08-27T14:39:28Z ddc:004 open_access

A Scalable and Unified Framework to Weighted Rank Aggregation Carmel, Amir Das, Debarati Nguyen, Tien-Long Rank aggregation 1-median Ulam distance Spearman’s footrule Kendall-tau Hamming distance weighted metrics Massively Parallel Computation Gromov product 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 (of size three or five), 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 (the size of a ranking) 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 (which may differ across metrics), 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, where computing the 1-median is NP-hard [Fischer et al., ESA, 2025], we simplify and strengthen the analysis of Chakraborty et al. [ITCS 2023], obtaining an improved 1.968-approximation that further extends to the weighted setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Carmel and Debarati Das and Tien-Long Nguyen 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.49 urn:nbn:de:0030-drops-264385 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.49 eng https://creativecommons.org/licenses/by/4.0/legalcode