Improved Differentially Private Algorithms for Rank Aggregation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908653398786048 |
|---|---|
| author | Hillebrand, Quentin Manurangsi, Pasin Suppakitpaisarn, Vorapong Vajanopath, Phanu |
| author_facet | Hillebrand, Quentin Manurangsi, Pasin Suppakitpaisarn, Vorapong Vajanopath, Phanu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11319 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Differentially Private Algorithms for Rank Aggregation Hillebrand, Quentin Manurangsi, Pasin Suppakitpaisarn, Vorapong Vajanopath, Phanu Data Structures and Algorithms Cryptography and Security 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. |
| title | Improved Differentially Private Algorithms for Rank Aggregation |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2511.11319 |