The complexity of scheduling TV commercials
Klemens Hägele, Colm Ó Dúnlaing, Søren Kamaric Riis · Electronic Notes in Theoretical Computer Science · 2001
Television commercial scheduling is a generalised form of partition problem, but the lengths involved are rather small, leaving the complexity of the problem unclear. This paper shows that the related problem of colour-restricted spot scheduling is NP-complete, even when the break-lengths are bounded (at most 18 units). We also show that scheduling unit-length spots is easy. The paper is intended to be self-contained.