Optimization Online


Streaming Cache Placement Problems: Complexity and Algorithms

Carlos A. S. Oliveira (oliveira***at***ufl.edu)
Panos M. Pardalos (pardalos***at***ufl.edu)
Oleg A. Prokopyev (prokopyev***at***ufl.edu)
Mauricio G. C. Resende (mgcr***at***att.com)

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.

Keywords: Multicast networks, streaming service placement, virtual private networks, computational complexity, algorithms.

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Network Optimization

Citation: AT&T Technical Report, May 30, 2003.

Download: [PDF]

Entry Submitted: 05/30/2003
Entry Accepted: 06/01/2003
Entry Last Modified: 12/09/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society