Many tasks in computer vision can be formulated as energy minimization problems. In this paper, we consider a natural class of energy functions that permits discontinuities. We show that minimizing these energy functions is NP-hard. However, the energy minimization problem can be solved by computing a minimum cost multiway cut on an associated graph. This allows the use of approximation algorithms that produce answers with quality guarantees. We present an efficient approximation algorithm that produces a local minimum even if very large moves are allowed. We apply our method to the tasks of image restoration and stereo. For both tasks we obtain promising results on data with ground truth.