The DOI matches its Crossref record; 159 of the 162 references it cites were found in a registry or an index.
Pseudo-Boolean optimization
Open accessOverview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 cited source says what the claim attributes to it.
In the citing paper
“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 [168]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
(1979) · Cited by 43,841
Neural networks and physical systems with emergent collective computational abilities.
Hopfield, J. J. (1982) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.79.8.2554 · Cited by 19,270
Theory of games and economic behavior
Garcia, S. R., & Miller, S. J. (2019) · American Mathematical Society eBooks · doi:10.1090/mbk/121/32 · Cited by 16,777
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Shapley, L. (1988) · Cambridge University Press eBooks · doi:10.1017/cbo9780511528446.003 · Cited by 10,698
17. A Value for n-Person Games
Shapley, L. S. (1953) · Contributions to the Theory of Games (AM-28), Volume II · doi:10.1515/9781400881970-018 · Cited by 6,950
Glover, F. (1990) · INFORMS journal on computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,777
Glover, F. (1989) · INFORMS journal on computing · doi:10.1287/ijoc.1.3.190 · Cited by 5,469
The Theory of Games and Economic Behavior
Harrison, R. W., von Neumann, J., & Morgenstern, O. (1945) · Journal of Farm Economics · doi:10.2307/1232672 · Cited by 5,318
Research works printed but not linked: 17
- T. Badics, Approximation of some Nonlinear Binary Optimization Problems, Ph.D. Thesis, RUTCOR, Rutgers University, 1996.
- Balas, 1967, Extension de l'algorithme additif a la programmation en nombres at a la programmation non lineare, C. R. Acad. Sci. Paris, 258, 5136
- Banzhaf III, 1965, Weighted voting does not work: a mathematical analysis, Rutgers Law Rev., 19, 317
- Benzaken, 1983, Adjoints of pure bidirected graphs, Congr. Numer., 39, 123
- Fortet, 1959, L'algebre de Boole en recherche operationelle, Cahiers Études Centre Rech. Oper., 1, 5
- Fortet, 1960, Applications de l'algebre de Boole en recherche operationelle, Rev. Francaise Rech. Oper., 4, 17
- Hammer, 1968, Plant location—a pseudo-Boolean approach, Israel J. Technol., 6, 330
- Hammer, 1977, Pseudo-Boolean functions and game theory. I. Core elements and Shapley value, Cahiers Centre Etudes Rech. Oper., 19, 159
- Hammer, 1963, Application of discrete linear programming to the minimization of Boolean functions, Rev. Math. Pures Appl., 8, 459
- P. Hansen, B. Simeone, A class of quadratic pseudoboolean functions whose maximization is reducible to a network flow problem, CORR 79-39, Department of Comb. Optim., University of Waterloo.
- Laughhunn, 1971, Computational experience with capital expenditure programming models under risk, J. Business Finance, 3, 43
- Rosenberg, 1972, 0–1 optimization and non-linear programming, Rev. Française Automatique, Informatique Rech. Opér. (Série Bleue), 2, 95
- Rosenberg, 1975, Reduction of bivalent maximization to the quadratic case, Cahiers Centre Etudes Rech. Oper., 17, 71
- Rosenberg, 1980, Linear decompositions of positive real function of binary arguments, Utilitas Math., 17, 17
- I. Shepanik, Use of pseudo-boolean preference functions in metagame analysis, Ph.D. Thesis, Department of System Design, 1973.
- B. Simeone, Quadratic 0–1 programming, Boolean functions and graphs, Ph.D. Thesis in Combinatorics and Optimization, Waterloo, 1979.
- Trubin, 1969, On a method of solution of integer linear programming problems of special kind, Soviet Math. Dokl., 10, 1544
Cited by
Sorted by citations
Items 701–800 of 825
Graph cuts with many-pixel interactions: Theory and applications to shape modelling
Freedman, D., & Turek, M. W. (2009) · Image and Vision Computing · doi:10.1016/j.imavis.2009.07.006
Approximability of Optimization Problems through Adiabatic Quantum Computation
Cruz-Santos, W., & Morales-Luna, G. B. (2014) · Synthesis lectures on quantum computing · doi:10.2200/s00596ed1v01y201409qmc009 · Cited by 1
Disjunctive analogues of submodular and supermodular pseudo-Boolean functions
Foldes, S., & Hammer, P. L. (2004) · Discrete Applied Mathematics · doi:10.1016/j.dam.2003.12.008
Self-citationCross-layer optimization in ultra wideband networks
Wu, Q., Bi, J., Guo, Z., Xiong, Y., Zhang, Q., & Li, Z. (2007) · Science in China Series F Information Sciences · doi:10.1007/s11432-007-0056-z
Optimality, flexibility and efficiency for cell formation in group technology
Krushynskyi, D. (2012) · University of Groningen research database (University of Groningen / Centre for Information Technology)
Parallelized Direct Search of a Binary Objective
Grant, P., & Walker, D. G. (2010) · Journal of Computing and Information Science in Engineering · doi:10.1115/1.3510589
Optimierung von Schulstundenplänen
Keck, P. (2014) · OPUS Publication Server of the University of Stuttgart (University of Stuttgart) · doi:10.18419/opus-3418
Sparse Higher Order Functions of Discrete Variables --- Representation and Optimization
Rother, C., & Kohli, P. (2011)
Balcárek, J., Fišer, P., & Schmidt, J. (2014) · Euromicro Conference on Digital System Design (DSD) · doi:10.1109/dsd.2014.86
Spokesmen Election Problem Revisited
Wang, W., & Soong, B. (2008) · IEEE Vehicular Technology Conference · doi:10.1109/vetecs.2008.397
2-Slave Dual Decomposition for Generalized Higher Order CRFs
Qian, X., & Liu, Y. (2014) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00187
SUPERVISED CLUSTERING WITH STRUCTURAL
Finley, T. (2009)
Algorithms for Parameterized Constraint Satisfaction Problems
Crowston, R. (2013)
Rossi, G. (2010)
Subset Algebra Lift Operators for 0-1 Integer Programming DRAFT ONLY. PLEASE DO NOT DISTRIBUTE
Bienstock, D., & Zuckerberg, M. (2002)
Persistency for higher-order pseudo-boolean maximization.
Strandmark, P. (2012) · Tiny Trans. Comput. Sci.
Efficient inference algorithms for near-deterministic systems
Chatterjee, S. (2013) · eScholarship (California Digital Library)
Ramos, T. (2015) · Revista E-Tech Tecnologias para Competitividade Industrial · doi:10.18624/e-tech.v8i2.854
Extending α-expansion to a larger set of regularization functions
Paget, M., Tarel, J., & Caraffa, L. (2015) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2015.7350960
Tangential Approximation of Surfaces
Olsson, C., & Boykov, Y. Y. (2014) · Actes des rencontres du CIRM · doi:10.5802/acirm.54
Prokopyev, O. A. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-24066-9.00074-x
Biamonte, J. (2010) · Oxford University Research Archive (ORA) (University of Oxford)
Graphical models for segmenting images, volumes and videos
Bhole, C., Pal, C., & Kautz, H. A. (2013) · UR Research (University of Rochester)
Guaranteed Parameter Estimation for Discrete Energy Minimization
Li, M., & Huber, D. (2017) · IEEE Winter Conference on Applications of Computer Vision · doi:10.1109/wacv.2017.59
Exploring Constraint Satisfiability Techniques in Formal Verification
Fang, L. (2008) · VTechWorks (Virginia Tech)
Decomposition of Trees and Paths via CorrelationPreprint
Lange, J.-H., & Andres, B. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.06822
On the complexity and approximation of the maximum expected value all-or-nothing subset
Goldberg, N., & Rudolf, G. (2019) · Discrete Applied Mathematics · doi:10.1016/j.dam.2019.08.012
A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
Letchford, A. N., & Grainger, D. J. (2017) · Operations Research Letters · doi:10.1016/j.orl.2017.10.007
Implementation of Image Segmentation with Graph Cut Method
Bawane, S. (2018) · International Journal for Research in Applied Science and Engineering Technology · doi:10.22214/ijraset.2018.3668
Rossi, G. (2019) · Lecture notes in networks and systems · doi:10.1007/978-3-030-12385-7_42
Caracterização da evolução adiabática em cadeias de spin
Grajales, J. A. V. (2018) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.76.2018.tde-05062018-151545
Learning dense 3D models from monocular video
Yu, R. (2017) · UCL Discovery (University College London)
Solving large Maximum Clique problems on a quantum annealerPreprint
Pelofske, E., Hahn, G., & Djidjev, H. N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.07657
Searching for network modulesPreprint
Rossi, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.07275
Higher Order Maximum Persistency and Comparison TheoremsPreprint
Shekhovtsov, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.00571
Diffusion Methods for Classification with Pairwise RelationshipsPreprint
Felzenszwalb, P. F., & Svaiter, B. F. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.06072
Efficient Energy Minimization for Enforcing StatisticsPreprint
Lim, Y., Jung, K., & Kohli, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.7800
A Discriminative View of MRF Pre-processing Algorithms
Wang, C., Herrmann, C., & Ramin Zabih, A. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.587
Maximum cut problem: new models
Kutucu, H., & Sharifov, F. A. (2020) · An International Journal of Optimization and Control Theories & Applications (IJOCTA) · doi:10.11121/ijocta.01.2020.00826
Exact MAP-Inference by Confining Combinatorial Search with LP RelaxationPreprint
Haller, S., Swoboda, P., & Savchynskyy, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.06370
A polynomial-time algorithm for optimization of quadratic pseudo-boolean functions
Martínez, M., & Ignacio, J. (2020)
Utilising duality in discrete tomography problems
Fleuren, S. (2020) · Utrecht University Repository (Utrecht University)
A Polynomial-Time Algorithm for Unconstrained Binary Quadratic OptimizationPreprint
Mulero-Martínez, J. I. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.07030
Multivariate arrival rate estimation using semidefinite programming
Papp, D., & Alizadeh, F. (2011) · Winter Simulation Conference · doi:10.1109/wsc.2011.6147982
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
Quadratization of gray coded representations, long path problems and needle functions
Whitley, D., Chicano, F., & Aguirre, H. E. (2021) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3449639.3459325
Inference and Decision in Credal Occupancy Grids: Use Case on Trajectory Planning
Masson, M.-H., Destercke, S., & Cherfaoui, V. B. (2021) · International Journal of Uncertainty Fuzziness and Knowledge-Based Systems · doi:10.1142/s0218488521500239
Polinomiális optimalizálási feladatok és relaxációik
Papp, D. (2021) · Alkalmazott Matematikai Lapok · doi:10.37070/aml.2021.38.1.07
Quadratic Optimization in 0–1 Variables
Billionnet, A. (2013) · doi:10.1002/9781118600245.ch8
Živný, S. (2012) · Cognitive technologies · doi:10.1007/978-3-642-33974-5_1
Paschos, V. T. (2014) · doi:10.1002/9781119005216.biblio
Autarkies and Persistencies for QUBO
Boros, E. (2022) · Springer eBooks · doi:10.1007/978-3-031-04520-2_5
Self-citationOptimización de una energía mediante cortes de grafos. Segmentación de imágenes
Puente, M. D. C. T. (2014) · UPM Digital Archive (Technical University of Madrid) · doi:10.20868/upm.thesis.33010
Benchmarking the recursive quantum approximate optimization algorithm
Frederick, P., Rines, R., Chong, F. T., & Gokhale, P. (2023) · Quantum Computing, Communication, and Simulation · doi:10.1117/12.2648434
An Order Reduction Design Framework for Higher-Order Binary Markov Random Fields
Chen, Z., Yang, H., & Liu, Y. (2023) · Entropy · doi:10.3390/e25030535
Dynamic Programming in Economics on a Quantum AnnealerPreprint
Fernández‐Villaverde, J., & Hull, I. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4475924
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
Feature Selection via Nonlinear Set Covering in Logical Analysis of Data
Yan, K., Xu, L., Zhao, Y., & Guo, C. X. (2023) · Journal of Circuits Systems and Computers · doi:10.1142/s0218126624500774
Random field optimization using local label hierarchy
Leelhapantu, S. (2017) · doi:10.58837/chula.the.2017.167
The Natural Bias of Artificial Instances
Unanue, I., Merino, M., & Lozano, J. A. (2023) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec53210.2023.10254020
Binary Integer Reformulations for Adiabatic Quantum Annealing HardwarePreprint
Barr, R. S., & Huskinson, T. (2023) · Research Square · doi:10.21203/rs.3.rs-3471221/v1
Network Analysis via Pseudo-Boolean Functions and Boole-Shannon Expansion
Alsalami, O. M., & Rushdi, A. M. A. (2023) · Journal of Advances in Mathematics and Computer Science · doi:10.9734/jamcs/2023/v38i111842
Characterization of rankings generated by pseudo-Boolean functions
Unanue, I., Merino, M., & Lozano, J. A. (2024) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2024.101540
Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination
Whitley, D., Ochoa, G., Floyd, N., & Chicano, F. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-57712-3_8
Using Constraint Propagation to Bound Linear Programs
Dlask, T., & Werner, T. (2024) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.15604
Pia, A. D., & Khajavirad, A. (2024) · Mathematical Programming · doi:10.1007/s10107-024-02122-y
Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
Walter, M. (2024) · Open Journal of Mathematical Optimization · doi:10.5802/ojmo.34
Data Correcting Approach for Routing and Location in Networks
Goldengorin, B. I. (2024) · Springer eBooks · doi:10.1007/978-1-4614-6624-6_84-1
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
Jordán, J., Palanca, J., Sánchez-Anguix, V., & Julián, V. (2025) · Complex & Intelligent Systems · doi:10.1007/s40747-024-01721-8
Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergencePreprint
Fujii, T., Komuro, K., & Tomari, K. (2025) · Research Square · doi:10.21203/rs.3.rs-6298629/v1
A Haskell Adiabatic DSL: Solving Classical Optimization Problems on Quantum Hardware
Li, L., Young, D., Graves, J. B., Dissanayake, C., & Sabry, A. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3747521
Encoding Binary Comparison Constraints in QUBO for Quantum Annealing
Codognet, P. (2025) · Genetic and Evolutionary Computation Conference Companion (GECCO Companion) · doi:10.1145/3712255.3734298
A Local Search and Cutting Plane Approach for Security-Constrained Unit Commitment Problems
Wang, M., Yu, Y., Ye, J., Huang, H., Chen, Y., Zhao, H., & Qian, M. (2025) · International Conference on Applied Mathematics, Modelling and Intelligent Computing (CAMMIC) · doi:10.1145/3745533.3745535
FMCooler: Simulated annealing for feature model configuration selection
Escánez-Expósito, D., Martinez, J., Osaba, E., & Caballero‐Gil, P. (2025) · International Software Product Line Conference (SPLC) · doi:10.1145/3748269.3748488
Applications of Pseudo-Boolean Polynomials in Medical Imaging
Chikake, T. M., Goldengorin, B. I., & Pardalos, P. M. (2025) · Springer eBooks · doi:10.1007/978-3-031-97461-8_3
Quantum Markov chain Monte Carlo method with programmable quantum simulators
D'Arcangelo, M., Javanmard, Y., & Pearson, N. (2026) · Physical Review A · doi:10.1103/7y57-1x19
Quantum Approaches for Degree-Constrained Minimum Spanning Tree Computation
do Carmo, R. S., Santana, M. C. S., Fanchini, F. F., da Costa, K. A. P., Rosalem, W. S., & Papa, J. P. (2025) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn64981.2025.11228458
Hybrid classical-quantum sampling for lattice scalar field theory
Kim, H., & Kim, J. (2025) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-025-00438-y
Wang, A., Cai, D., Zhang, Y., Huang, Y., Feng, X., & Zhang, Z. (2025) · Physical Review Research · doi:10.1103/knt1-yd9s
Local techniques in quadratic optimization and Satisfiability, and their applications
Wang, C. (2014) · Summit (Simon Fraser University)
Issue Prioritization in Agile Development Through the Lens of Constraint Solving
Salmon, T.-L., MacIsaac, D., & Palma, F. (2025) · IEEE International Conference on Collaborative Advances in Software and Computing (CASCON) · doi:10.1109/cascon66301.2025.00070
Efficient and Verifiable Proof Logging for MaxSAT Solving
Doren, R. V., Antonopoulos, T., & Piskač, R. (2025) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase63991.2025.00113
Chikake, T. M., Goldengorin, B. I., & Pardalos, P. M. (2025) · Computer Optics · doi:10.18287/coj1815
Ji, N., Zheng, G., Zhang, J., Krikidis, I., & Wong, K. (2026) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2026.3672548
Khabour, F. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6446862
Lagrangian Based Approaches for Lexicalized Tree Adjoining Grammar Parsing
Corro, C. (2018) · theses.fr (ABES) · doi:10.70675/dba406f0zbcd0z4091z922czacad086660f4
Applications of machine learning to the resolution of recurrent combinatorial optimization problems
Mossina, L. (2020) · theses.fr (ABES) · doi:10.70675/69eb2c60z998cz4ff6zaef7z4d002022bc97
Ji, N., Zheng, G., & Guo, Y. (2026) · IEEE Communications Letters · doi:10.1109/lcomm.2026.3680950
Annotation-efficient learning for object discovery and detection
Vo, H. V. (2022) · theses.fr (ABES) · doi:10.70675/aae8cd95z8e92z4d35z9384zafe56efdad87
Certified graph-cut separation for 3-additive capacities via signed switching
Huang, J., & Chen, C.-Y. (2026) · Fuzzy Sets and Systems · doi:10.1016/j.fss.2026.109911
Metadata
- Authors
- Boros, E., & Hammer, P. L.
- Affiliations
- Rutgers, The State University of New Jersey (US)
- Corresponding author
- Boros, Endre
- Venue
- Discrete Applied Mathematics
- Publisher
- Elsevier BV
- Published
- 2002-11
- Volume
- 123
- Issue
- 1-3
- Pages
- 155-225
- ISSN
- 0166-218X (ISSN-L)
- OpenAlex
- W2074078071
- Cited by
- 827
- References
- 162
- Citations by year
- 2026: 34 · 2025: 34 · 2024: 27 · 2023: 33 · 2022: 32 · 2021: 28 · 2020: 35 · 2019: 39 · 2018: 42 · 2017: 38 · 2016: 35 · 2015: 43 · 2014: 62 · 2013: 58 · 2012: 52
- FWCI
- 9.97
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- Locations
- Discrete Applied Mathematics (publishedVersion)
- Rutgers University Community Repository (Rutgers University) (submittedVersion)
- ORBi (University of Liège) (submittedVersion, other-oa)
- Funders
- National Science Foundation (9806389)
- Office of Naval Research (N00014-92-J-1375, N00014)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- pseudo-Boolean optimization, set functions, algebraic expressions, approximation algorithms, combinatorial optimization
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
