Journal
OPTIMIZATION LETTERS
Volume 13, Issue 1, Pages 81-94Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-018-1251-0
Keywords
Scheduling; TV rating points; Dynamic programming; Fully polynomial time approximation scheme; K-approximation sets and functions
Funding
- FONDECYT [11140566]
- Universidad de Santiago
- DICYT [061817VP]
- Israel Science Foundation [399/17]
Ask authors/readers for more resources
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).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available