The TV advertisements scheduling problem

A TV channel has a single advertisement break of duration h and a convex continuous function f[0,h] -> R+ representing the TV rating points within the advertisement break. Given n TV advertisements of different durations pj that sum up to h, and willingness to pay coefficients wj, the objective is to schedule them on the TV break in order to maximize the total revenue of the TV channel Sigma jwjcj-pjcjf(t)dt, where [cj-pj,cj) is the broadcast time interval of TV advertisement j. We show that this problem is NP-hard and propose a fully polynomial time approximation scheme, using a special dominance property of an optimal schedule and the technique of K-approximation sets and functions introduced by Halman et al. (Math Oper Res 34:674-685, 2009).