In the cover-decomposition problem we are given a ground set of points and a collection of its subsets. Suppose that we want to colour some subsets blue and the others red, so that every point lies in both a blue subset and a red subset. An obvious necessary condition is that every point lies in at least two subsets; is there an exact or approximate converse? What about when there are many colours? Using probabilistic methods and iterated linear programming we'll give positive answers in some settings. This is joint work with Bela Bollobas, Thomas Rothvoss and Alex Scott.