  We consider a variational convex relaxation of a class of optimal
partitioning and multiclass labeling problems, which has recently proven quite
successful and can be seen as a continuous analogue of Linear Programming (LP)
relaxation methods for finite-dimensional problems. While for the latter case
several optimality bounds are known, to our knowledge no such bounds exist in
the continuous setting. We provide such a bound by analyzing a probabilistic
rounding method, showing that it is possible to obtain an integral solution of
the original partitioning problem from a solution of the relaxed problem with
an a priori upper bound on the objective, ensuring the quality of the result
from the viewpoint of optimization. The approach has a natural interpretation
as an approximate, multiclass variant of the celebrated coarea formula.
