Streaming cache
placement problems: Complexity and algorithms

C.A.S.
Oliveira, P.M. Pardalos, O. Prokopyev, and M.G.C. Resende
International J. of
Computational Science and Engineering, vol. 3, pp. 173-183, 2007.

**ABSTRACT**

Virtual private networks (VPN) are often used to distribute live
content, such as video or audio streams, from a single source to a
large number of destinations. Streaming caches or splitters are
deployed in these multicast networks to allow content distribution
without overloading the network. In this paper, we consider two
combinatorial optimization problems that arise in multicast
networks. In the Tree Cache Placement Problem (TCPP), the
objective is to find a routing tree on which the number of cache nodes
needed for multicasting is minimized. We also discuss a
modification of this problem, called the Flow Cache Placement Problem
(FCPP), where we seek any feasible flow from the source to the
destinations which minimizes the number of cache nodes. We prove
that these problems are NP-hard using a transformation from
Satisfiability. This transformation allows us to give a proof of
non-approximability by showing that it is gap-preserving. We also
consider approximation algorithms for the TCPP and FCPP and special
cases where these problems can be solved in polynomial time.

PDF file of paper

DjVu file of
paper

Go back

Mauricio G.C.
Resende's Home Page

Last modified: *12 June 2008*
Copyright Notice