Quadratization of symmetric pseudo-Boolean functions

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

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

Robust Higher Order Potentials for Enforcing Label Consistency

Kohli, P., Ladický, Ľ., & Torr, P. H. S. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0202-0 · Cited by 858 · see citing works

Pseudo-Boolean optimization

Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · see citing works

Exact optimization for markov random fields with convex priors

Ishikawa, H. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1233908 · Cited by 487 · see citing works

Optimizing Binary MRFs via Extended Roof Duality

Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2007.383203 · Cited by 424 · see citing works

Minimizing Nonsubmodular Functions with Graph Cuts-A Review

Kolmogorov, V., & Rother, C. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1031 · Cited by 362 · see citing works

Boolean Functions: Theory, Algorithms, and Applications

Crama, Y., & Hammer, P. L. (2011) · Open Repository and Bibliography (University of Liège) · Cited by 327 · see citing works

A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems

Kappes, J. H., Andres, B., Hamprecht, F. A., Schnörr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B. X., Lellmann, J., Nikos Komodakis, A., et al. (2013) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2013.175 · Cited by 195 · see citing works

Energy Minimization via Graph Cuts: Settling What is Possible

Freedman, D., & Drineas, P. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.143 · Cited by 173 · see citing works

Minimizing sparse higher order energy functions of discrete variables

Rother, C., Kohli, P., Feng, W., & Jia, J. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206739 · Cited by 161 · see citing works

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

Discrete Neural Computation: A Theoretical Foundation

Siu, K.-Y. S., Roychowdhury, V., & Kailath, T. (1995) · Medical Entomology and Zoology · Cited by 116 · see citing works

P³ & Beyond: Move Making Algorithms for Solving Higher Order Functions

Kohli, P., Kumar, M., & Torr, P. H. S. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.217 · Cited by 99 · see citing works

TRANSFORMING AN ARBITRARY MINSUM PROBLEM INTO A BINARY ONE

Schlesinger, D., & Flach, B. (2006) · Cited by 96 · see citing works

Quadratic reformulations of nonlinear binary optimization problems

Anthony, M., Boros, E., Crama, Y., & Gruber, A. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1032-4 · Cited by 90 · see citing works

Surveys in Combinatorics, 1993

(1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662089 · Cited by 83 · see citing works

A graph cut algorithm for higher-order Markov Random Fields

Fix, A., Gruber, A., Boros, E., & Ramin Zabih, A. (2011) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2011.6126347 · Cited by 81 · see citing works

Slicing the hypercube

Saks, M. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662089.009 · Cited by 80 · see citing works

Size--Depth Tradeoffs for Threshold Circuits

Impagliazzo, R., Paturi, R., & Saks, M. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539792282965 · Cited by 64 · see citing works

The threshold order of a Boolean function

Wang, C., & Williams, A. C. (1991) · Discrete Applied Mathematics · doi:10.1016/0166-218x(91)90032-r · Cited by 50 · see citing works

The expressive power of binary submodular functions

Živný, S., Cohen, D. A., & Jeavons, P. (2009) · Discrete Applied Mathematics · doi:10.1016/j.dam.2009.07.001 · Cited by 47 · see citing works

On Quadratization of Pseudo-Boolean Functions

Boros, E., & Gruber, A. (2014) · arXiv · doi:10.48550/arxiv.1404.6538 · Cited by 32 · see citing works

Efficient minimization of higher order submodular functions using monotonic Boolean functions

Ramalingam, S., Russell, C., Ladický, Ľ., & Torr, P. H. S. (2017) · Discrete Applied Mathematics · doi:10.1016/j.dam.2016.11.022 · Cited by 23 · see citing works

A Tutorial on Formulating and Using QUBO ModelsPreprint

Glover, F., Kochenberger, G. A., & Du, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.11538 · Cited by 273 · see citing works

Quadratic reformulations of nonlinear binary optimization problems

Anthony, M., Boros, E., Crama, Y., & Gruber, A. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1032-4 · Cited by 90 · 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

Prime factorization using quantum annealing and computational algebraic geometry

Dridi, R., & Alghassi, H. (2017) · Scientific Reports · doi:10.1038/srep43048 · Cited by 75 · see citing works

Quadratization in discrete optimization and quantum mechanicsPreprint

Dattani, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.04405 · Cited by 56 · see citing works

Compact quadratizations for pseudo-Boolean functions

Boros, E., Crama, Y., & Rodríguez-Heck, E. (2019) · Journal of Combinatorial Optimization · doi:10.1007/s10878-019-00511-0 · Cited by 35 · see citing works

Linear and quadratic reformulations of nonlinear optimization problems in binary variables

Rodríguez-Heck, E. (2018) · 4OR · doi:10.1007/s10288-018-0392-4 · Cited by 24 · see citing works

A QUBO Formulation of the Stereo Matching Problem for D-Wave Quantum Annealers

Cruz-Santos, W., Venegas-Andraca, S. E., & Lanzagorta, M. O. (2018) · Entropy · doi:10.3390/e20100786 · Cited by 21 · see citing works

Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions

Verma, A., & Lewis, M. W. (2019) · Optimization Letters · doi:10.1007/s11590-019-01460-7 · Cited by 21 · 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

Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables

Boros, E., Crama, Y., & Rodríguez-Heck, E. (2018) · ORBi (University of Liège) · Cited by 7 · see citing works

Machine-Cell and Part-Family Formation via Neurodynamics-Driven Constrained Binary Matrix Factorization

Li, H., & Wang, J. (2025) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2025.3613713 · Cited by 6 · see citing works

Quadratization and convexification in polynomial binary optimization

Crama, Y., Elloumi, S., Lambert, A., & Rodríguez-Heck, E. (2025) · Journal of Combinatorial Optimization · doi:10.1007/s10878-025-01334-y · Cited by 5 · see citing works

Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences

Clausen, J., Crama, Y., Lusby, R. M., Rodríguez-Heck, E., & Røpke, S. (2024) · Computers & Operations Research · doi:10.1016/j.cor.2024.106586 · Cited by 4 · see citing works

An initial step toward a quantum annealing approach to the discrete logarithm problem

Mahasinghe, A., & Jayasinghe, Y. (2022) · Security and Privacy · doi:10.1002/spy2.234 · Cited by 3 · see citing works

Quadratic Reformulation of Nonlinear Pseudo-Boolean Functions via the Constraint Composite Graph

Yip, K.-W., Xu, H., Koenig, S., & Kumar, T. K. S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-19212-9_43 · Cited by 3 · see citing works

Algorithmic and complexity results for boolean and pseudo-boolean functions

Gruber, A. (2015) · doi:10.7282/t3pz5bhq · Cited by 2 · see citing works

Hybrid Quantum-Classical Algorithms for Solving the Weighted CSP.

Xu, H., Sun, K., Koenig, S., Hen, I., & Kumar, T. K. S. (2020) · International Symposium on Artificial Intelligence and Mathematics · Cited by 2 · see citing works

Semiconductor Scheduling Problem Based on K-Mode Clustering Algorithm

Xie, F. (2021) · Lecture notes in electrical engineering · doi:10.1007/978-981-16-0115-6_97 · Cited by 1 · see citing works

Local Search with Configuration Checking for PBS

Han, R., Wang, J., & Li, X. (2017) · doi:10.1145/3168390.3168396

Polyhedral Analysis of Symmetric Multilinear Polynomials over Box ConstraintsPreprint

Xu, Y., Adams, W. P., & Gupte, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.06394

An Order Reduction Design Framework for Higher-Order Binary Markov Random Fields

Chen, Z., Yang, H., & Liu, Y. (2023) · Entropy · doi:10.3390/e25030535

Solving Unconstrained Binary Polynomial Programs with Limited ReachPreprint

Clausen, J., Crama, Y., Lusby, R. M., Rodríguez-Heck, E., & Røpke, S. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4530363

Recursive McCormick Linearization of Multilinear Programs

Cardonha, C., Raghunathan, A. U., Bergman, D., & Nohra, C. (2025) · INFORMS journal on computing · doi:10.1287/ijoc.2023.0390

Pseudo-Boolean Polynomial Method for InterpreTab. Dimensionality Reduction: A Paradigm Shift from Abstract to Meaningful Feature Extraction

Chikake, T. M., Goldengorin, B. I., & Pardalos, P. M. (2025) · Computer Optics · doi:10.18287/coj1815

Global optimization of polynomial programs with mixed-integer variables

Lazare, A. (2019) · doi:10.70675/d7492c96z0224z44d4z947bz4f1b9a7a49d5

Quadratizations of pseudo-Boolean functions

Crama, Y. (2015) · ORBi (University of Liège)

Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables

Boros, E., Crama, Y., & Rodríguez-Heck, E. (2018) · ORBi (University of Liège) · Cited by 7 · see citing works

Quadratic reformulations of nonlinear binary optimization problems

Crama, Y. (2013) · Open Repository and Bibliography (University of Liège)

Compact quadratizations for pseudo-Boolean functions

Boros, E., Crama, Y., & Rodríguez-Heck, E. (2019) · Journal of Combinatorial Optimization · doi:10.1007/s10878-019-00511-0 · Cited by 35 · see citing works

All 4-variable functions can be perfectly quadratized with only 1 auxiliary variablePreprint

Dattani, N., & Chau, H. T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.13583 · Cited by 2 · see citing works