Name
Abstract | ||
|---|---|---|
Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top K items from noisy pairwise comparisons. In our setting, we are non-actively given r pairwise comparisons between each pair of n items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top-K problem. In particular, we present a linear time algorithm for the top-K problem which has a competitive ratio of [EQUATION]; i.e. to solve any instance of top-K, our algorithm needs at most [EQUATION] times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top-K problem have competitive ratios of O(n) or worse). We further show that this is tight: any algorithm for the top-K problem has competitive ratio at least [EQUATION].
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.5555/3039686.3039767 | SODA '17: Symposium on Discrete Algorithms
Barcelona
Spain
January, 2017 |
DocType | Volume | ISBN |
Journal | abs/1605.03933 | 978-1-61197-503-1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xi Chen | 1 | 399 | 31.78 |
| Sivakanth Gopi | 2 | 25 | 5.63 |
| Jieming Mao | 3 | 54 | 9.19 |
| Jon Schneider | 4 | 3 | 5.06 |