How to aggregate Top-lists: Approximation algorithms via scores and average ranks
| Autor: | Simon Mauras, Claire Mathieu |
|---|---|
| Přispěvatelé: | Department of Computer Science (Brown University), Brown University |
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Generalization Sorting Approximation algorithm Aggregation problem Randomized algorithm Computer Science - Information Retrieval Combinatorics Ranking Computer Science - Data Structures and Algorithms Rank (graph theory) [INFO]Computer Science [cs] Data Structures and Algorithms (cs.DS) Time complexity ComputingMilieux_MISCELLANEOUS Information Retrieval (cs.IR) Mathematics |
| Zdroj: | SODA Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2020 Proceedings of the 2020 Symposium on Discrete Algorithms, 2020, Jan 2020, Salt Lake City, United States. pp.2810-2822, ⟨10.1137/1.9781611975994.171⟩ |
| DOI: | 10.48550/arxiv.1811.01537 |
| Popis: | A top-list is a possibly incomplete ranking of elements: only a subset of the elements are ranked, with all unranked elements tied for last. Top-list aggregation, a generalization of the well-known rank aggregation problem, takes as input a collection of top-lists and aggregates them into a single complete ranking, aiming to minimize the number of upsets (pairs ranked in opposite order in the input and in the output). In this paper, we give simple approximation algorithms for top-list aggregation. * We generalize the footrule algorithm for rank aggregation. * Using inspiration from approval voting, we define the score of an element as the frequency with which it is ranked, i.e. appears in an input top-list. We reinterpret Ailon's RepeatChoice algorithm for top-list aggregation using the score of an element and its average rank given that it is ranked. * Using average ranks, we generalize and analyze Borda's algorithm for rank aggregation. * We design a simple 2-phase variant of the Generalized Borda's algorithm, roughly sorting by scores and breaking ties by average ranks. * We then design another 2-phase variant in which in order to break ties we use, as a black box, the Mathieu-Schudy PTAS for rank aggregation, yielding a PTAS for top-list aggregation. * Finally, we discuss the special case in which all input lists have constant length. Comment: To appear in SODA'20 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|