Video distribution under multiple constraints

We consider the optimization problem of providing a set of video streams to a set of clients, where each stream has costs in m possible measures (such as communication bandwidth, processing bandwidth, etc.), and each client has its own utility function for each stream. We assume that the server has a budget cap on each of the m cost measures; each client has an upper bound on the utility that can be derived from it, and potentially also upper bounds in each of the m cost measures. The task is to choose which streams the server will provide, and out of this set, which streams each client will receive. The goal is to maximize the overall utility subject to the budget constraints. We give an efficient approximation algorithm with approximation factor of O ( m ) with respect to the optimal possible utility for any input, assuming that clients have only a bound on their maximal utility. If, in addition, each client has at most m c capacity constraints, then the approximation factor increases by another factor of O ( m c log n ), where n is the input length. We also consider the special case of “small” streams, namely where each stream has cost of at most O ( 1 / log n ) fraction of the budget cap, in each measure. For this case we present an algorithm whose approximation ratio is O ( log n ).

Authors

• Boaz Patt-Shamir
• Dror Rawitz

Keywords

• Approximation algorithms
• Budgeted set cover
• Resource allocation
• Scheduling
• Video distribution