Energy Minimization via Graph Cuts: Settling What is Possible
Abstract
The recent explosion of interest in graph cut methods in computer vision naturally spawns the question: what energy functions can be minimized via graph cuts? This question was first attacked by two papers of Kolmogorov and Zabih, in which they dealt with functions with pair-wise and triplewise pixel interactions. In this work, we extend their results in two directions. First, we examine the case of k-wise pixel interactions; the results are derived from a purely algebraic approach. Second, we discuss the applicability of provably approximate algorithms. Both of these developments should help researchers best understand what can and cannot be achieved when designing graph cut based algorithms.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The potentially large overhead in the number of variables lead to the development of several methods for degree reduction.
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188])”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [180]
Cites
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988 · see citing works
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · American Mathematical Monthly · doi:10.2307/2322374 · Cited by 6,007 · see citing works
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,098 · see citing works
Combinatorial optimization:Algorithms and complexity
Rabiner, L. R. (1984) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1984.1164450 · Cited by 3,590 · see citing works
What energy functions can be minimized via graph cuts?
Kolmogorov, V., & Zabih, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262177 · Cited by 3,127 · see citing works
Monte Carlo Strategies in Scientific Computing
Liu, J. S. (2004) · Springer series in statistics · doi:10.1007/978-0-387-76371-2 · Cited by 2,734 · see citing works
Monte Carlo Strategies in Scientific Computing
Hesterberg, T. (2002) · Technometrics · doi:10.1198/tech.2002.s85 · Cited by 1,418 · see citing works
Multi-camera Scene Reconstruction via Graph Cuts
Kolmogorov, V., & Ramin Zabih, A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-47977-5_6 · Cited by 745 · see citing works
Proof verification and hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267823 · Cited by 740 · see citing works
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442696 · Cited by 569 · see citing works
Self-citationComputing geodesics and minimal surfaces via graph cuts
Boykov, & Kolmogorov (2003) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2003.1238310 · Cited by 555 · see citing works
An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
Barahona, F., Grötschel, M., Jünger, M., & Reinelt, G. (1988) · Operations Research · doi:10.1287/opre.36.3.493 · Cited by 505 · see citing works
Quick Approximation to Matrices and Applications
FRIEZE, A. M., & Kannan, R. (1999) · COMBINATORICA · doi:10.1007/s004930050052 · Cited by 503 · see citing works
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
Petros Drineas, B., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442684 · Cited by 479 · see citing works
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (1999) · IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.1999.791245 · Cited by 479 · see citing works
An Algorithmic Theory of Numbers, Graphs and Convexity
Lovász, L. (1986) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970203 · Cited by 359 · see citing works
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442702 · Cited by 326 · see citing works
Self-citation.879-approximation algorithms for MAX CUT and MAX 2SAT
Goemans, M. X., & Williamson, D. P. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195216 · Cited by 234 · see citing works
Polynomial time approximation schemes for dense instances of NP -hard problems
Arora, S., Karger, D. R., & Karpiński, M. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225140 · Cited by 203 · see citing works
The Approximability of Constraint Satisfaction Problems
Khanna, S., Sudan, M., Trevisan, L., & Williamson, D. P. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799349948 · Cited by 196 · see citing works
878-approximation Algorithms for MAX CUT and MAX 2SAT
Goemans, M. X. (1994) · Symposium on the Theory of Computing · Cited by 173 · see citing works
The regularity lemma and approximation schemes for dense problems
FRIEZE, A. M., & Kannan, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548459 · Cited by 170 · see citing works
Random sampling and approximation of MAX-CSPs
Alon, N., de la Véga, W. F., Kannan, R., et al. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00008-4 · Cited by 100 · see citing works
Maximum cuts and large bipartite subgraphs
Poljak, S., & Tuza, Ź. (1995) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/020/04 · Cited by 83 · see citing works
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548493 · Cited by 82 · see citing works
MAX-CUT has a randomized approximation scheme in dense graphs
de la Véga, W. F. (1996) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199605)8:3 · Cited by 79 · see citing works
The complexity of massive data set computations
Bar-Yossef, Z., & Papadimitriou, C. H. (2002) · Cited by 64 · see citing works
Random sampling and approximation of MAX-CSP problems
Alon, N., de la Véga, W. F., Kannan, R., et al. (2002) · doi:10.1145/509907.509945 · Cited by 57 · see citing works
Sampling lower bounds via information theory
Bar-Yossef, Z. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780593 · Cited by 41 · see citing works
Proof verification and the hardness of approximation problems.
Arora, S., Lund, C., Motwani, R., et al. (1998) · Cited by 26 · see citing works
A Polynomial Time Approximation Scheme for Subdense MAX-CUTPreprint
de la, V. W. F., & Marek, K. (2002) · Electronic colloquium on computational complexity · Cited by 7 · see citing works
Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms
Drineas, P., Kannan, R., & Mahoney, M. W. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31856-9_5 · Cited by 7 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Transformation of General Binary MRF Minimization to the First-Order Case
Ishikawa, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.91 · Cited by 144 · see citing works
A cross-disciplinary introduction to quantum annealing-based algorithms
Venegas-Andraca, S. E., Cruz-Santos, W., McGeoch, C., & Lanzagorta, M. (2018) · Contemporary Physics · doi:10.1080/00107514.2018.1450720 · Cited by 83 · see citing works
Quadratization of symmetric pseudo-Boolean functions
Anthony, M., Boros, E., Crama, Y., & Gruber, A. (2016) · Discrete Applied Mathematics · doi:10.1016/j.dam.2016.01.001 · Cited by 26 · see citing works
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188]), which are explained and compared in References [53, 62, 135, 218].”
Method
- Authors
- Freedman, D., & Drineas, P.
- Affiliations
- Rensselaer Polytechnic Institute (US)
- Venue
- 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05)
- Publisher
- IEEE
- Published
- 2005-07-27
- Volume
- 2
- Pages
- 939-946
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2135165032
- Cited by
- 173
- References
- 32
- Citations by year
- 2026: 3 · 2025: 5 · 2024: 7 · 2023: 10 · 2022: 7 · 2021: 5 · 2020: 8 · 2019: 10 · 2018: 5 · 2017: 3 · 2016: 7 · 2015: 8 · 2014: 8 · 2013: 8 · 2012: 10
- FWCI
- 5.98
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Keywords
- graph cuts, energy minimization, pairwise interactions, approximate algorithms, image segmentation, algebraic characterization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
