25/02/2026 11:17 AM - PACES
Aidan Dempster - adempst - 6125 9596
Problem
Energy minimization over graphs is in general an NP-hard problem. Methods like simulated annealing are prone to getting stuck in local minima and have fast growing runtimes.
Approach
Instead of changing one pixel at a time, let's allow a large number of pixels to swap simulaneously. Choosing the set of pixels to swap is a combinatorial problem so would have exponential runtime, but we can use a local energy minimization found using a min-cut to reduce this runtime. This substantially reduces the overall runtime of the algorithm.
Contribution
The authors propose the graph cut algorithm for the solution of energy minimization and prove that it converges to known factor of the true minimum energy given that the energy function has a relatively loose set of requirements it satisfies.
Evaluation
Proofs: The paper proves the NP-hardness of the underlying problem and the optimality bounds of the algorithm that approximately solves the problem.
Empirical Eval: The paper also provides a set of example uses like denoising and stereo correspondance that show convergence in real world senarios.
Substantiation
As we have become accustom to in these papers, the evaluation show the validity of the method and performance on well known tasks, but does not do large scale comparisons. In this case we do get a direct comparison to another method, simulated annealing, but due to the lack of large well labeled datasets even this evaluation is sparse.
Fast_approximate_energy_minimization_via_graph_cuts.pdf