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
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y. E., & Nemirovski, A. S. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,396
Future paths for integer programming and links to artificial intelligence
Glover, F. (1986) · Computers & Operations Research · doi:10.1016/0305-0548(86)90048-1 · Cited by 4,370
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Complexity of Computer Computations
Miller, R. E., Thatcher, J. W., & Bohlinger, J. D. (1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,914
Amit, D. J. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511623257 · Cited by 2,261
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,223
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · COMBINATORICA · doi:10.1007/bf02579273 · Cited by 2,037
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Contributions to the theory of games.
Volume, I. V. (1960) · Journal of the Franklin Institute · doi:10.1016/0016-0032(60)90366-5 · Cited by 1,851
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
Raghavan, P., & Tompson, C. D. (1987) · COMBINATORICA · doi:10.1007/bf02579324 · Cited by 1,021
The Quadratic Assignment Problem
Lawler, E. L. (1963) · Management Science · doi:10.1287/mnsc.9.4.586 · Cited by 978
Submodular functions and convexity
Lovász, L. (1983) · Springer eBooks · doi:10.1007/978-3-642-68874-4_10 · Cited by 968
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
Mathematical Programming The State of the Art
Bachem, A., Grötschel, M., & Korte, B. H. (1983) · Springer eBooks · doi:10.1007/978-3-642-68874-4 · Cited by 728
Johnson, D. S., Papadimitriou, C. H., & Yannakakis, M. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90046-3 · Cited by 714
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
Schrijver, A. (2000) · Journal of Combinatorial Theory Series B · doi:10.1006/jctb.2000.1989 · Cited by 678
Vertex packings: Structural properties and algorithms
Nemhauser, G. L., & Trotter, L. E. (1975) · Mathematical Programming · doi:10.1007/bf01580444 · Cited by 663
Stecke, K. E. (1983) · Management Science · doi:10.1287/mnsc.29.3.273 · Cited by 659
Cluster analysis and mathematical programming
Hansen, P., & Jaumard, B. (1997) · Mathematical Programming · doi:10.1007/bf02614317 · Cited by 653
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
Raghavan, P. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90003-7 · Cited by 550
Boolean Methods in Operations Research and Related Areas
Hammer, P. L., & Rudeanu, S. (1968) · Ökonometrie und Unternehmensforschung · doi:10.1007/978-3-642-85823-9 · Cited by 529
Self-citationInteractive proofs and the hardness of approximating cliques
Feige, U., Goldwasser, S., Lovász, L., Safra, M., & Szegedy, M. (1996) · Journal of the ACM · doi:10.1145/226643.226652 · Cited by 525
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
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 454
Balas, E., & Padberg, M. W. (1976) · SIAM Review · doi:10.1137/1018115 · Cited by 453
Solvable spin systems with random interactions
Mattis, D. C. (1976) · Physics Letters A · doi:10.1016/0375-9601(76)90396-0 · Cited by 415
Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
Glover, F., & Woolsey, E. (1974) · Operations Research · doi:10.1287/opre.22.1.180 · Cited by 404
Cluster Analysis and Mathematical Programming
Rao, M. R. (1971) · Journal of the American Statistical Association · doi:10.1080/01621459.1971.10482319 · Cited by 377
Barahona, F., & Mahjoub, A. R. (1986) · Mathematical Programming · doi:10.1007/bf02592023 · Cited by 374
Algorithms for the maximum satisfiability problem
Hansen, P., & Jaumard, B. (1990) · Computing · doi:10.1007/bf02241270 · Cited by 370
Modeling Brain Function: The World of Attractor Neural Networks
de Callataÿ, A. (1990) · Trends in Neurosciences · doi:10.1016/0166-2236(90)90155-4 · Cited by 361
The boolean quadric polytope: Some characteristics, facets and relatives
Padberg, M. W. (1989) · Mathematical Programming · doi:10.1007/bf01589101 · Cited by 356
Collective computational properties of neural networks: New learning mechanisms
Personnaz, L., Guyon, I., & Dreyfus, G. (1986) · Physical Review A · doi:10.1103/physreva.34.4217 · Cited by 333
Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
Feige, U., & Goemans, M. X. (2002) · Israel Symposium on Theory and Computing Systems (ISTCS) · doi:10.1109/istcs.1995.377033 · Cited by 328
Roof duality, complementation and persistency in quadratic 0–1 optimization
Hammer, P. L., Hansen, P., & Simeone, B. (1984) · Mathematical Programming · doi:10.1007/bf02612354 · Cited by 318
Self-citationCapital Budgeting of Interrelated Projects: Survey and Synthesis
Weingartner, H. M. (1966) · Management Science · doi:10.1287/mnsc.12.7.485 · Cited by 298
Probabilistic checking of proofs; a new characterization of NP
Arora, S., & Safra, M. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267824 · Cited by 283
Free bits, PCPs and non-approximability-towards tight results
Bellare, M., Goldreich, O., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492573 · Cited by 271
Cooperative Games on Combinatorial Structures
Bilbao, J. M. (2000) · Theory and decision library. Series C, Game theory, mathematical programming and operations research · doi:10.1007/978-1-4615-4393-0 · Cited by 258
Solving satisfiability in less than 2n steps
Monien, B., & Speckenmeyer, E. (1985) · Discrete Applied Mathematics · doi:10.1016/0166-218x(85)90050-2 · Cited by 255
A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
Adams, W. P., & Sherali, H. D. (1986) · Management Science · doi:10.1287/mnsc.32.10.1274 · Cited by 255
Minimum cuts and related problems
Picard, J., & Ratliff, H. D. (1975) · Networks · doi:10.1002/net.3230050405 · Cited by 246
A Selection Problem of Shared Fixed Costs and Network Flows
Rhys, J. (1970) · Management Science · doi:10.1287/mnsc.17.3.200 · Cited by 241
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
Goemans, M. X., & Williamson, D. P. (1994) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480192243516 · Cited by 232
Methods of Nonlinear 0-1 Programming
Hansen, P. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70343-1 · Cited by 222
Watters, L. J. (1967) · Operations Research · doi:10.1287/opre.15.6.1171 · Cited by 220
Franklin, J. (1980) · Undergraduate texts in mathematics · doi:10.1007/978-1-4613-9447-1_2 · Cited by 206
On the Approximation of Maximum Satisfiability
Yannakakis, M. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1045 · Cited by 201
Some Network Flow Problems Solved with Pseudo-Boolean Programming
Ivanescu, P. L. (1965) · Operations Research · doi:10.1287/opre.13.3.388 · Cited by 170
Balas, E., & Padberg, M. W. (1972) · Operations Research · doi:10.1287/opre.20.6.1152 · Cited by 169
A 7/8-approximation algorithm for MAX 3SAT?
Karloff, H. J., & Zwick, U. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646129 · Cited by 168
Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm
Simone, C. D., Diehl, M., Jünger, M., Mutzel, P., Reinelt, G., & Rinaldi, G. (1995) · Journal of Statistical Physics · doi:10.1007/bf02178370 · Cited by 160
Quadratic Binary Programming with Application to Capital-Budgeting Problems
Laughhunn, D. J. (1970) · Operations Research · doi:10.1287/opre.18.3.454 · Cited by 144
Zwick, U. (1998) · doi:10.5555/314613.314701 · Cited by 143
The cut polytope and the Boolean quadric polytope
Simone, C. D. (1990) · Discrete Mathematics · doi:10.1016/0012-365x(90)90056-n · Cited by 139
Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
Nemhauser, G. L., & Wolsey, L. A. (1981) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)73471-6 · Cited by 138
Glover, F., & Woolsey, E. (1973) · Operations Research · doi:10.1287/opre.21.1.156 · Cited by 130
Combinatorial optimization models for production scheduling in automated manufacturing systems
Crama, Y. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00388-8 · Cited by 122
The Evaluation of Risky Interrelated Investments
Beckmann, M. J., & Hillier, F. S. (1973) · International Statistical Review · doi:10.2307/1402636 · Cited by 118
Nonlinear 0–1 programming: I. Linearization techniques
Balas, E., & Mazzola, J. B. (1984) · Mathematical Programming · doi:10.1007/bf02591796 · Cited by 115
Approximations of pseudo-Boolean functions; applications to game theory
Hammer, P. L., & Holzman, R. (1992) · Mathematical Methods of Operations Research · doi:10.1007/bf01541028 · Cited by 111
Self-citationConstrained Nonlinear 0-1 Programming
Hansen, P., Jaumard, B., & Mathon (1989) · Les Cahiers du GERAD · Cited by 101
The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds
Boros, E., & Hammer, P. L. (1991) · Annals of Operations Research · doi:10.1007/bf02115753 · Cited by 91
Self-citationA Cut Approach to the Rectilinear Distance Facility Location Problem
Picard, J., & Ratliff, H. D. (1978) · Operations Research · doi:10.1287/opre.26.3.422 · Cited by 86
Some remarks on quadratic programming with 0-1 variables
Hammer, P. L., & Rubin, A. A. (1970) · Revue française d informatique et de recherche opérationnelle Série verte · doi:10.1051/ro/197004v300671 · Cited by 83
Self-citationFacets of the Bipartite Subgraph Polytope
Barahona, F., Grötschel, M., & Mahjoub, A. R. (1985) · Mathematics of Operations Research · doi:10.1287/moor.10.2.340 · Cited by 79
The basic algorithm for pseudo-Boolean programming revisited
Crama, Y., Hansen, P., & Jaumard, B. (1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90142-y · Cited by 78
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
Iwata, S., Fleischer, L., & Fujishige, S. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335317 · Cited by 75
Complexity of Partial Satisfaction
Lieberherr, K. J., & Specker, E. P. (1981) · Journal of the ACM · doi:10.1145/322248.322260 · Cited by 73
A solvable case of quadratic 0–1 programming
Barahona, F. (1986) · Discrete Applied Mathematics · doi:10.1016/0166-218x(86)90065-x · Cited by 72
One-pass heuristics for large-scale unconstrained binary quadratic problems
Glover, F., Alidaee, B., Rego, C., & Kochenberger, G. A. (2002) · European Journal of Operational Research · doi:10.1016/s0377-2217(01)00209-0 · Cited by 71
Gadgets, approximation, and linear programming
Trevisan, L., Sorkin, G. B., Sudan, M., & Williamson, D. P. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548521 · Cited by 69
Nonlinear 0–1 programming: II. Dominance relations and algorithms
Balas, E., & Mazzola, J. B. (1984) · Mathematical Programming · doi:10.1007/bf02591797 · Cited by 66
Billionnet, A., & Minoux, M. (1985) · Discrete Applied Mathematics · doi:10.1016/0166-218x(85)90035-6 · Cited by 65
Concave extensions for nonlinear 0–1 maximization problems
Crama, Y. (1993) · Mathematical Programming · doi:10.1007/bf01582138 · Cited by 65
Badics, T., & Boros, E. (1998) · Mathematics of Operations Research · doi:10.1287/moor.23.3.649 · Cited by 64
Self-citationHill Climbing with Multiple Local Optima
Tovey, C. A. (1985) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0606040 · Cited by 63
New results on the completion time variance minimization
Kubiak, W. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(93)e0125-i · Cited by 60
Vertices Belonging to All or to No Maximum Stable Sets of a Graph
Hammer, P. L., Hansen, P., & Simeone, B. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603052 · Cited by 60
Self-citationDeza, M. M., & Laurent, M. (1992) · Mathematical Programming · doi:10.1007/bf01580897 · Cited by 58
Upper-bounds for quadratic 0–1 maximization
Boros, E., Crama, Y., & Hammer, P. L. (1990) · Operations Research Letters · doi:10.1016/0167-6377(90)90044-6 · Cited by 56
Self-citationRecognition problems for special classes of polynomials in 0–1 variables
Crama, Y. (1989) · Mathematical Programming · doi:10.1007/bf01587085 · Cited by 53
On the supermodular knapsack problem
Gallo, G., & Simeone, B. (1989) · Mathematical Programming · doi:10.1007/bf01589108 · Cited by 52
Pseudo-Boolean Functions and Stability of Graphs
Ebenegger, C., Hammer, P. L., & de Werra, D. (1984) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)72955-4 · Cited by 51
Self-citationOn the integer-valued variables in the linear vertex packing problem
Picard, J., & Queyranne, M. (1977) · Mathematical Programming · doi:10.1007/bf01593772 · Cited by 46
Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
Boros, E., & Hammer, P. L. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.1.245 · Cited by 46
Self-citationJohnson, D. S., Papadimitriou, C. H., & Yannakakis, M. (1985) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1985.31 · Cited by 46
(0, 1) hyperbolic programming problems
Robillard, P. N. (1971) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800180104 · Cited by 45
Facets for the cut cone II: Clique-web inequalities
Deza, M. M., & Laurent, M. (1992) · Mathematical Programming · doi:10.1007/bf01580898 · Cited by 41
Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
Boros, E., Crama, Y., & Hammer, P. L. (1992) · SIAM Journal on Discrete Mathematics · doi:10.1137/0405014 · Cited by 37
Self-citationAlgorithms for minclique scheduling problems
Jurisch, B., Kubiak, W., & Józefowska, J. (1997) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(96)00040-6 · Cited by 36
Hansen, P., & Simeone, B. (1986) · Discrete Applied Mathematics · doi:10.1016/0166-218x(86)90031-4 · Cited by 35
Adams, W. P., & Dearing, P. M. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(92)00119-7 · Cited by 34
The struction of a graph: Application toCN-free graphs
Hammer, P. L., Mahadev, N. V. R., & de Werra, D. (1985) · COMBINATORICA · doi:10.1007/bf02579377 · Cited by 30
Self-citationOn the Maximization of a Pseudo-Boolean Function
Hammer, P. L., & Peled, U. N. (1972) · Journal of the ACM · doi:10.1145/321694.321700 · Cited by 29
Self-citationRoof duality for polynomial 0–1 optimization
Lu, S. H., & Williams, A. C. (1987) · Mathematical Programming · doi:10.1007/bf02591742 · Cited by 29
From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
Hammer, P. L., Simeone, B., Liebling, T. M., & de Werra, D. (1988) · SIAM Journal on Discrete Mathematics · doi:10.1137/0401019 · Cited by 29
Self-citationLow order polynomial bounds on the expected performance of local improvement algorithms
Tovey, C. A. (1986) · Mathematical Programming · doi:10.1007/bf01580647 · Cited by 27
Maximizing the Product of Two Linear Functions In 0-1 Variables
Hammer, P. L., Hansen, P., Pardalos, P. M., & Rader, D. J. (2002) · Optimization · doi:10.1080/02331930290009847 · Cited by 27
Self-citationBoolean query optimization and the 0-1 hyperbolic sum problem
Hansen, P., de Aragão, M. V. P., & Ribeiro, C. C. (1990) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/bf01531072 · Cited by 26
Probabilistic bounds and algorithms for the maximum satisfiability problem
Boros, E., & Prékopa, A. (1989) · Annals of Operations Research · doi:10.1007/bf02022095 · Cited by 25
Self-citationUnconstrained 0–1 optimization and Lagrangean relaxation
Adams, W. E., Billionnet, A., & Sutter, A. (1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90139-4 · Cited by 25
A strongly polynomial-time algorithm for minimizing submodular functions
Iwata, S., Fleischer, L., & Fujishige, S. (1999) · Cited by 24
Polynomially solvable cases for the maximum stable set problem
Hertz, A. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)00051-e · Cited by 24
Hammer, P. L., Mahadev, N. V. R., & de Werra, D. (1985) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(85)90089-9 · Cited by 24
Self-citationCombinatorial mathematics: Proceedings of the Third International Conference
Bloom, G. S., Graham, R., & Malkevitch, J. (1989) · Medical Entomology and Zoology · Cited by 23
Approximation algorithms for the maximum satisfiability problem
Asano, T., Ono, T., & Hirata, T. (1996) · Nordic journal of computing · Cited by 21
Optimal Test Generation in Combinational Networks by Pseudo-Boolean Programming
Papaioannou (1977) · IEEE Transactions on Computers · doi:10.1109/tc.1977.1674880 · Cited by 21
Pseudo-Boolean remarks on balanced graphs
Hammer, P. L. (1977) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-5936-3_5 · Cited by 20
Self-citationQuadratic functions of binary variables
Hammer, P. L., & Simeone, B. (1989) · Lecture notes in mathematics · doi:10.1007/bfb0083461 · Cited by 20
Self-citationOn the equivalence of paved-duality and standard linearization in nonlinear 0–1 optimization
Hansen, P., Lu, S. H., & Simeone, B. (1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90143-z · Cited by 19
Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
Boros, E., Hammer, P. L., Minoux, M., & Rader, D. J. (1999) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(98)00114-0 · Cited by 19
Self-citationApplications of pseudo-Boolean methods to economic problems
Hammer, P. L., & Shlifer, E. (1971) · Theory and Decision · doi:10.1007/bf00139572 · Cited by 18
Self-citationStrong unimodularity for matrices and hypergraphs
Crama, Y., Hammer, P. L., & Ibaraki, T. (1986) · Discrete Applied Mathematics · doi:10.1016/0166-218x(86)90044-2 · Cited by 17
Self-citationPersistency in quadratic 0–1 optimization
Billionnet, A., & Sutter, A. (1992) · Mathematical Programming · doi:10.1007/bf01586044 · Cited by 16
On the use of Boolean methods for the computation of the stability number
Hertz, A. (1997) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(96)00124-2 · Cited by 15
Covering Non-uniform Hypergraphs
Boros, E., Caro, Y., Füredi, Z., & Yuster, R. (2001) · Journal of Combinatorial Theory Series B · doi:10.1006/jctb.2001.2037 · Cited by 14
Self-citationMaximum renamable Horn sub-CNFs
Boros, E. (1999) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(99)00031-1 · Cited by 14
Self-citationPseudo-Boolean Solutions to Multidimensional Location Problems
Warszawski, A. (1974) · Operations Research · doi:10.1287/opre.22.5.1081 · Cited by 14
Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdos inequality
Bylka, S., Idzik, A., & Tuza, Ź. (1999) · Discrete Mathematics · doi:10.1016/s0012-365x(98)00115-0 · Cited by 14
Quadratic functions with exponential number of local maxima
Kalantari, B. (1986) · Operations Research Letters · doi:10.1016/0167-6377(86)90100-8 · Cited by 13
Multiple optima in local search
Rödl, V., & Tovey, C. A. (1987) · Journal of Algorithms · doi:10.1016/0196-6774(87)90041-1 · Cited by 13
Quasimonotone Boolean Functions and Bistellar Graphs
Hammer, P. L., & Simeone, B. (1980) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70043-8 · Cited by 12
Self-citationLinear Decomposition of a Positive Group-Boolean Function
Hammer, P. L., & Rosenberg, I. G. (1974) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-5321-7_5 · Cited by 12
Self-citationUPPER PLANES OF QUADRATIC 0–1 FUNCTIONS AND STABILITY IN GRAPHS
Hammer, P. L., Hansen, P., & Simeone, B. (1981) · Elsevier eBooks · doi:10.1016/b978-0-12-468662-5.50019-7 · Cited by 12
Self-citationAN ALGORITHM FOR MAXIMUM LIKELIHOOD RANKING AND SLATER'S i FROM PAIRED COMPARISONS
Ranyard, R. (1976) · British Journal of Mathematical and Statistical Psychology · doi:10.1111/j.2044-8317.1976.tb00715.x · Cited by 12
Young, A. P. (1984) · Journal of Statistical Physics · doi:10.1007/bf01009446 · Cited by 12
Pseudo-Boolean Functions and Their Graphs
Fraenkel, A. S., & Hammer, P. L. (1984) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)72817-2 · Cited by 11
Self-citationCrama, Y., & Mazzola, J. B. (1995) · Annals of Operations Research · doi:10.1007/bf02032163 · Cited by 11
Average Performance of Heuristics for Satisfiability
Kohli, R., & Krishnamurti, R. (1989) · SIAM Journal on Discrete Mathematics · doi:10.1137/0402046 · Cited by 10
A Characterization of a Cone of Pseudo-Boolean Functions via Supermodularity-Type Inequalities
Crama, Y., Hammer, P. L., & Holzman, R. (1989) · Springer eBooks · doi:10.1007/978-3-642-74306-1_4 · Cited by 9
Self-citationA bound on the roof-duality gap
Hammer, P. L., & Kalantari, B. (1989) · Lecture notes in mathematics · doi:10.1007/bfb0083469 · Cited by 8
Self-citationGadgets, Approximation, and Linear Programming (extended abstract).
Trevisan, L., Sorkin, G. B., Sudan, M., & Williamson, D. P. (1996) · Cited by 8
BOOLEAN-COMBINATORIAL BOUNDING OF MAXIMUM 2-SATISFIABILITY
Bourjolly, J.-M., Hammer, P. L., Pulleyblank, W. R., & Simeone, B. (1992) · Elsevier eBooks · doi:10.1016/b978-0-08-040806-4.50007-1 · Cited by 8
Self-citationSimeone, B., & estivo, C. I. M. (1989) · Lecture notes in mathematics · doi:10.1007/bfb0083460 · Cited by 7
On Some Properties of the Struction of a Graph
de Werra, D. (1984) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0605025 · Cited by 7
More characterizations of triangulated graphs
Benzaken, C., Crama, Y., Duchet, P., Hammer, P. L., & Maffray, F. (1990) · Journal of Graph Theory · doi:10.1002/jgt.3190140404 · Cited by 7
Self-citationSome Remarks on Conflict Graphs of Quadratic Pseudo-Boolean Functions
Benzaken, C., Hammer, P. L., & Simeone, B. (1980) · International series of numerical mathematics · doi:10.1007/978-3-0348-6322-3_1 · Cited by 6
Self-citationThe struction algorithm for the maximum stable set problem revisited
Hoke, K., & Troyon, M. (1994) · Discrete Mathematics · doi:10.1016/0012-365x(94)90377-8 · Cited by 6
Quelques utilisations de la struction
Hertz, A. (1986) · Discrete Mathematics · doi:10.1016/0012-365x(86)90071-3 · Cited by 6
Recognition of Quadratic Graphs and Adjoints of Bidirected Graphsa
Crama, Y., & Hammer, P. L. (1989) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1989.tb22445.x · Cited by 5
Self-citationBimatroidal independence systems
Crama, Y., & Hammer, P. L. (1989) · Mathematical Methods of Operations Research · doi:10.1007/bf01423645 · Cited by 5
Self-citationA linear pseudo-Boolean viewpoint on matching and other central concepts in graph theory
Nieminen, J. (1974) · Applicationes Mathematicae · doi:10.4064/am-14-3-365-369 · Cited by 4
Quantitative methoden in den wirtschaftswissenschaften
Kall, P., Kohlas, W., Popp, W., & Zehnder, C. A. (1990) · European Journal of Operational Research · doi:10.1016/0377-2217(90)90168-b · Cited by 4
Sur la résolution des programmes fractionnaires en variables 0-1
Nagih, A. (1996) · Cited by 3
Ein effektiver Branch and Bound‐Algorithmus für Boolesche quadratische Optimierungsprobleme
Körner, F. (1985) · ZAMM ‐ Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik · doi:10.1002/zamm.19850650820 · Cited by 3
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
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 3,070
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000001 · Cited by 2,041
Learning to Discover Social Circles in Ego Networks
Leskovec, J., & McAuley, J. (2012) · neural information processing systems · Cited by 1,701
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
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
