The complexity of scheduling TV commercials

Source: https://www.maths.tcd.ie/report_series/abstracts/tcdm0009.html Parent: https://www.maths.tcd.ie/research/papers/

The complexity of scheduling TV commercials

Television commercial scheduling is a generalised form of bin-packing problem, but the bins are rather small, leaving the complexity of the problem unclear. This paper shows that if breaks can be restricted to admit only certain colours, then the problem is NP-complete, even when the breaks are at most 10 units long. We also show that scheduling unit-length spots is easy.

The paper is intended to be self-contained.