An FPTAS for managing playout stalls for multiple video streams in cellular networks

With the proliferation of wireless cellular technology (e.g., 5G, 4G LTE), managing quality of experience (QoE) for wireless clients streaming different videos over these networks is becoming increasingly important. In this paper, we consider the problem of managing playout stalls experienced by multiple clients streaming different videos from a cellular base station. We build on our prior work [1], where we formulate an epoch based lead aware multiple video transmission (LMVT) problem to minimize the total number of playout stalls experienced by mobile clients. In [1], [2], we show that the LMVT problem is NP-hard and propose a pseudo polynomial dynamic programming solution and a simple greedy heuristic to solve the problem. In this paper, we first show that even a simpler and less restrictive version of the LMVT problem remains hard. We then design a fully polynomial time approximation scheme (FPTAS) for the LVMT problem by demonstrating that it is equivalent to the Santa Claus Problem [3], [4]. The FPTAS provides a bounded performance guarantee, differing by a factor of 1/1+ϵB from the optimal solution (where B is the number of time slots in an epoch and ε is a small constant).