We give an overview over recent developments on provably optimal relaxation of partitioning problems and on important implementation aspects. Moreover we present some new results on using non-convex higher-order regularization for a special class of interpolation problems.