LP-Based Optimization of Storage and Retrieval for Distributed Video-on-Demand
The authors first formulate the optimization problem to an integer program. To address its tractability, they propose a novel, effective and implementable heuristic. The heuristic, termed LP-SR decomposes the problem into two computationally efficient Linear Programs (LPs) for segment storage and retrieval, respectively. The strength of LP-SR is that it is asymptotically optimal in terms of k, and k does not need to be high to achieve near optimality (around 5 to 10 in their study). Through extensive simulation study, LP-SR is shown to perform significantly the best as compared with other state-of-the-art and traditional schemes, reducing the deployment cost by a wide margin (by multiple times in many cases).