17 marca 2026 10:15
[Seminarium ZOK] Phanu Vajanopath: Improved Differentially Private Algorithms for Rank Aggregation
Abstract:
The Kemeny rank aggregation problem aims to combine multiple ranks
into a single consensus ranking minimizing the total pairwise
disagreement with the input rankings. This problem is known to be a
special case of the Minimum Feedback Arc Set problem on tournaments.
Alabi, Ghazi, Kumar, and Manurangsi (AAAI 2022) present differentially
private (DP) polynomial-time approximation schemes (PTASes) and
5-approximation algorithms with certain additive errors for the Kemeny
rank aggregation problem in both the central and local models.
In this work, we present improved DP PTASes with smaller additive
errors in the central model. Furthermore, we also present
2-approximation algorithms with the same additive error as the
5-approximation algorithms of Alabi et al. for the Kemeny rank
aggregation problem in both the central and local models.
Joint work with Quentin Hillebrand, Vorapong Suppakitpaisarn, and
Pasin Manurangsi.