This paper presents two efficient algorithms for minimizing energy functions in early vision tasks. The algorithms use graph cuts to find local minima, even when large label changes are allowed. The first algorithm, based on α-β swaps, finds a labeling where no swap can decrease the energy. The second algorithm, based on α-expansion, finds a labeling where no expansion can decrease the energy, and the solution is within a known factor of the global minimum. The energy function is composed of a smoothness term and a data term. The smoothness term involves only pairs of pixels and can be a semi-metric or metric. The algorithms are applied to image restoration, stereo, and motion tasks, demonstrating their effectiveness. The swap algorithm works for any semi-metric, while the expansion algorithm requires the smoothness term to be a metric. The algorithms are efficient, with the swap algorithm requiring O(|L|²) iterations and the expansion algorithm requiring O(|L|) iterations per cycle. The expansion algorithm guarantees a solution within a known factor of the global minimum. The paper also discusses the theoretical foundations of the algorithms, including the correspondence between graph cuts and labelings, and the properties of the energy functions. Experimental results show that the algorithms outperform simulated annealing in terms of speed and accuracy.This paper presents two efficient algorithms for minimizing energy functions in early vision tasks. The algorithms use graph cuts to find local minima, even when large label changes are allowed. The first algorithm, based on α-β swaps, finds a labeling where no swap can decrease the energy. The second algorithm, based on α-expansion, finds a labeling where no expansion can decrease the energy, and the solution is within a known factor of the global minimum. The energy function is composed of a smoothness term and a data term. The smoothness term involves only pairs of pixels and can be a semi-metric or metric. The algorithms are applied to image restoration, stereo, and motion tasks, demonstrating their effectiveness. The swap algorithm works for any semi-metric, while the expansion algorithm requires the smoothness term to be a metric. The algorithms are efficient, with the swap algorithm requiring O(|L|²) iterations and the expansion algorithm requiring O(|L|) iterations per cycle. The expansion algorithm guarantees a solution within a known factor of the global minimum. The paper also discusses the theoretical foundations of the algorithms, including the correspondence between graph cuts and labelings, and the properties of the energy functions. Experimental results show that the algorithms outperform simulated annealing in terms of speed and accuracy.