Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks
Source: Cybernetics and Systems Analysis, Volume 41, Number 6, November 2005 , pp. 898-908(11)
Abstract:The streaming cache placement problem (SCPP) is considered. The SCPP is known to be NP-hard and MAX SNP-hard. It is shown that for the SCPP there is no approximation algorithm with a guarantee better than log k unless NP can be solved in sub-exponential time. Construction algorithms for the SCPP, based on two general techniques, are proposed. The results of computational experiments based on these two algorithms and their modifications are reported.
Document Type: Research Article
Publication date: November 2005