Approximation guarantees for the joint optimization of caching and recommendation

Costantini, Marina; Spyropoulos, Thrasyvoulos; Giannakas, Theodoros; Sermpezis, Pavlos
ICC 2020, IEEE International Conference on Communications
7-11 June 2020, Dublin, Ireland (Virtual Conference)

Caching popular content at the network edge can benefit both the operator and the client by alleviating the backhaul traffic and reducing access latency, respectively.
Recommendation systems, on the other hand, try to offer interesting content to the user and impact her requests, but independently of the caching policy. Nevertheless, it
has been recently proposed that designing caching and recommendation policies separately is suboptimal. Caching could benefit by knowing the recommender’s actions in advance, and recommendation algorithms could try to favor cached content (among equally interesting options) to improve network performance and user experience. In this paper we tackle the problem of optimally making caching and recommendation decisions jointly, in the context of the recently introduced “soft cache hits” setup. We show that even the simplest (one user, one cache) problem is NP-hard, but that the most generic problem (multiple users, femtocaching network) is approximable to a constant. To the best of our knowledge, this is the first polynomial algorithm with approximation guarantees for the joint problem. Finally, we compare our algorithm to existing schemes using a range of real-world data-sets.

Communication systems
Eurecom Ref:
© 2020 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.