The advertisement knapsack problem

We consider the problem of selecting and scheduling TV advertisements to fill a commercial break as effectively as possible. The gain generated by selecting and airing an ad depends on the ad’s profit and on the position in the break where the ad is scheduled, the latter being represented by an impact function. The resulting problem turns out to be a generalization of the Knapsack Problem, for which we revise and extend results from the literature and show strong NP-hardness in its general form. Then, we focus on the relevant case where the impact function is negative unimodal. For this case, we introduce two new relaxations based on splitting ads into time slices, determine their worst-case optimality gaps, and introduce constructive algorithms for their computation. In addition, a dynamic programming algorithm is introduced for computing an exact solution of the problem. Finally, we present three greedy-type algorithms and analyze their worst-case performance guarantee.