Streaming cache placement problems: complexity and algorithms
Carlos Augusto Silva de Oliveira, Pãnos M. Pardalos, Oleg A. Prokopyev, Maurício G. C. Resende · International Journal of Computational Science and Engineering · 2007
Multicast networks are used to distribute live content, such as video or audio streams, to a potentially large number of destinations. Streaming caches are deployed in these multicast systems to allow content distribution without network overload. We consider two related problems that arise in multicast networks: the tree cache placement and the flow cache placement problems. These problems are shown to be NP-hard, and we give a proof of hardness of approximation using a gap-preserving reduction. We also present approximation algorithms, as well as special cases where these problems can be solved in polynomial time.