Streaming cache placement problems: complexity and algorithms. (22nd April 2008)

• Record Type: Journal Article
• Authors: Oliveira, Carlos A.S.; Pardalos, Panos M.; Prokopyev, Oleg A.; Resende, Mauricio G.C.
• Is Part Of: International journal of computational science and engineering. Volume 3:Number 3(2007)
• Page Start: 173
• Page End: 183
• Publication Date: 2008-04-22
• Subjects: multicast networks -- streaming service placement -- virtual private networks -- computational complexity -- approximation algorithms -- streaming caches -- tree cache placement -- flow cache placement; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

Abstract

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.