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(nlog2⁡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(log2⁡n)O(log2⁡n) multiplicative factor from optimal in this sense.