Beyond a Single Consensus: Algorithms for Diverse Rank Aggregation

Rank aggregation combines potentially conflicting rankings into a consensus minimizing its total distance to the inputs. Yet many applications require multiple substantially different but equally good consensuses to accommodate heterogeneous needs or information not captured by the aggregation objective. Given an integer $k$, diverse rank aggregation seeks $k$ optimal consensuses maximizing a diversity objective. We study this problem under the Spearman footrule distance for three standard objectives: diameter (the case of $k=2$), sum dispersion, and min dispersion. The only prior theoretical work considered sum dispersion under Kendall–tau distance from a fixed-parameter-complexity perspective [Arrighi et al., IJCAI'21]; we initiate the study of the polynomial-time approximation landscape. While standard rank aggregation under the Spearman footrule is solvable in polynomial time, the complexity of its diverse variants remained open. We give polynomial-time exact algorithms for diameter and sum dispersion using new doubled- and $k$-copy matching formulations over the tight-edge assignment graph. In contrast, we show that min dispersion is NP-hard for every fixed $k\ge 3$. Since the notion of min dispersion coincides with diameter for $k=2$, this yields a sharp complexity dichotomy. For fixed $k$, we give a randomized factor-$2$ approximation based on an exact robust-farthest oracle (algorithm): given selected optimal aggregates, it finds another maximizing its minimum distance from them. We design this algorithm using a multivariate determinant, interpolation, and self-reduction, and prove it NP-hard for unbounded $k$. When $k$ is part of the input, a polynomial-time multiplicative-weights algorithm ensures that every pair has expected distance at least half the optimum, up to any prescribed additive error. We further study diverse solution generation also for near-optimal aggregate rankings. We complement our theoretical study with empirical results on multiple real-world datasets. Our algorithms attain the optimal sum-dispersion value, perform strongly on min dispersion against natural matching- and solver-based baselines, and furthermore, return rankings that remain highly diverse even under Kendall–tau distance.