Submodular functions capture a variety of discrete problems in machine learning, signal processing and computer vision. In these areas, practical algorithms are a major concern. Luckily, the submodular functions occurring in practice often have additional structure that can be exploited for practically efficient optimization algorithms. One such structure is that of functions decomposing as a sum of "simple" submodular functions. Building on relations to convexity, several algorithms arise. This talk will focus on a class of algorithms that, based on a specific relaxation, solve the submodular minimization problem as a best approximation problem. These algorithms are easy to use and parallelize, and solve both the convex relaxation and the original discrete problem. We observe that the algorithms work well in practice, and analyze their convergence properties. This is joint work with Robert Nishihara, Francis Bach, Suvrit Sra and Michael I. Jordan.