On competitive recommendations
详细信息 查看全文
- 作者：Jara Uitto ; juitto@tik.ee.ethz.ch" class="auth_mail" title="E-mail the corresponding author ; Roger Wattenhofer
- 关键词：Learning ; Online ; Recommendation ; Algorithms
- 刊名：Theoretical Computer Science
- 出版年：2016
- 出版时间：21 March 2016
- 年：2016
- 卷：620
- 期：Complete
- 页码：4-14
- 全文大小：364 K
文摘
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 ee2ee0071e99908">
overhead in comparison to the weaker offline solution. Furthermore, we show that the corresponding overhead for any online algorithm is , which shows that the performance of our algorithm is within an eed88f295872941" title="Click to view the MathML source">O(log2n) multiplicative factor from optimal in this sense.
overhead in comparison to the weaker offline solution. Furthermore, we show that the corresponding overhead for any online algorithm is , which shows that the performance of our algorithm is within an eed88f295872941" title="Click to view the MathML source">O(log2n) multiplicative factor from optimal in this sense.