  We consider the problem of minimizing the sum of submodular set functions
assuming minimization oracles of each summand function. Most existing
approaches reformulate the problem as the convex minimization of the sum of the
corresponding Lov\'asz extensions and the squared Euclidean norm, leading to
algorithms requiring total variation oracles of the summand functions; without
further assumptions, these more complex oracles require many calls to the
simpler minimization oracles often available in practice. In this paper, we
consider a modified convex problem requiring constrained version of the total
variation oracles that can be solved with significantly fewer calls to the
simple minimization oracles. We support our claims by showing results on graph
cuts for 2D and 3D graphs
