# 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.