Making recommendations bandwidth aware
Authors:
- Linqi SongLSLinqi Song
- Christina FragouliCFChristina Fragouli
Preprint
Abstract
This paper asks how much we can gain in terms of bandwidth and user satisfaction, if recommender systems became bandwidth aware and took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. We formulate this as a new problem in the context of index coding: we relax the index coding requirements to capture scenarios where each client has preferences associated with messages. The client is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We consistently find, over a number of scenarios we sample, that although the optimization problems are in general NP-hard, significant bandwidth savings are possible even when restricted to polynomial time algorithms.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The Minrank of Random GraphsIEEE Transactions on Information Theory, 2018
- A polynomial-time algorithm for pliable index coding2016
- Pliable Index CodingIEEE Transactions on Information Theory, 2015
- An Equivalence Between Network Coding and Index CodingIEEE Transactions on Information Theory, 2015
- A social recommender mechanism for location-based group commerceInformation Sciences, 2014
- Index Coding With Side InformationIEEE Transactions on Information Theory, 2011
- On the Hardness of Approximating the Network Coding CapacityIEEE Transactions on Information Theory, 2011
- On the Index Coding Problem and Its Relation to Network Coding and Matroid TheoryIEEE Transactions on Information Theory, 2010
- Nonlinear Index Coding Outperforming the Linear OptimumIEEE Transactions on Information Theory, 2009
- A note on greedy algorithms for the maximum weighted independent set problemDiscrete Applied Mathematics, 2003