EUVIMEDEUVIMED entdecken
Crossref

Improved Differentially Private Algorithms for Rank Aggregation

Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (20) · 17032-17039

DOI: 10.1609/aaai.v40i20.38751 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Quentin Hillebrand und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Rank aggregation is a task of combining the rankings of items from multiple users into a single ranking that best represents the users' rankings. Alabi et al. (AAAI'22) presents differentially-private (DP) polynomial-time approximation schemes (PTASes) and 5-approximation algorithms with certain additive errors for the Kemeny rank aggregation problem in both central and local models. In this paper, we present improved DP PTASes with smaller additive error in the central model. Furthermore, we are first to study the footrule rank aggregation problem under DP. We give a near-optimal algorithm for this problem; as a corollary, this leads to 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 central and local models.

Zitieren

APA

Hillebrand, Q., Manurangsi, P., Suppakitpaisarn, V., & Vajanopath, P. (2026). Improved Differentially Private Algorithms for Rank Aggregation. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 17032-17039. https://doi.org/10.1609/aaai.v40i20.38751

Vancouver

Hillebrand Q, Manurangsi P, Suppakitpaisarn V, Vajanopath P. Improved Differentially Private Algorithms for Rank Aggregation. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(20):17032-17039. doi:10.1609/aaai.v40i20.38751

BibTeX
@article{Hillebrand2026,
  author = {Hillebrand, Quentin and Manurangsi, Pasin and Suppakitpaisarn, Vorapong and Vajanopath, Phanu},
  title = {Improved Differentially Private Algorithms for Rank Aggregation},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {20},
  pages = {17032--17039},
  doi = {10.1609/aaai.v40i20.38751}
}
Kostenlos starten →