On competitive recommendations

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 O ( n log 2 ⁡ n ) overhead in comparison to the weaker offline solution. Furthermore, we show that the corresponding overhead for any online algorithm is Ω ( n ), which shows that the performance of our algorithm is within an O ( log 2 ⁡ n ) multiplicative factor from optimal in this sense.

Authors

• Jara Uitto
• Roger Wattenhofer ETH Zurich

Keywords

• Learning
• Online
• Recommendation
• Algorithms