On Competitive Recommendations
Abstract
We are given an unknown binary matrix, where the entries correspond to preferences of users on items. We want to find at least one 1-entry in each row with a minimum number of queries. The number of queries needed heavily depends on the input matrix and a straightforward competitive analysis yields bad results for any online algorithm. Therefore, we analyze our algorithm against a weaker offline algorithm that is given the number of users and a probability distribution according to which the preferences of the users are chosen. We show that our algorithm has an $\mathcal{O}(\sqrt{n} \log^2 n)$ overhead in comparison to the weaker offline solution. Furthermore, we show that the corresponding overhead for any online algorithm is $\Omega(\sqrt{n})$ , which shows that the performance of our algorithm is within an $\mathcal{O}(\log^2 n)$ multiplicative factor from optimal.
Cite
Text
Uitto and Wattenhofer. "On Competitive Recommendations." International Conference on Algorithmic Learning Theory, 2013. doi:10.1007/978-3-642-40935-6_7Markdown
[Uitto and Wattenhofer. "On Competitive Recommendations." International Conference on Algorithmic Learning Theory, 2013.](https://mlanthology.org/alt/2013/uitto2013alt-competitive/) doi:10.1007/978-3-642-40935-6_7BibTeX
@inproceedings{uitto2013alt-competitive,
title = {{On Competitive Recommendations}},
author = {Uitto, Jara and Wattenhofer, Roger},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2013},
pages = {83-97},
doi = {10.1007/978-3-642-40935-6_7},
url = {https://mlanthology.org/alt/2013/uitto2013alt-competitive/}
}