Pseudo-Boolean optimization
Open accessThe 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
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 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 [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.
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 · see citing works
(1979) · Cited by 43,841 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Shapley, L. (1988) · Cambridge University Press eBooks · doi:10.1017/cbo9780511528446.003 · Cited by 10,698 · see citing works
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 · see citing works
Glover, F. (1990) · INFORMS journal on computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,676 · see citing works
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,258 · see citing works
Glover, F. (1989) · INFORMS journal on computing · doi:10.1287/ijoc.1.3.190 · Cited by 5,122 · see citing works
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 · see citing works
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 · see citing works
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,370 · see citing works
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,198 · see citing works
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
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,789 · see citing works
Amit, D. J. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511623257 · Cited by 2,279 · see citing works
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 · see citing works
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,057 · see citing works
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902 · see citing works
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,837 · see citing works
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 · see citing works
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 · see citing works
The Quadratic Assignment Problem
Lawler, E. L. (1963) · Management Science · doi:10.1287/mnsc.9.4.586 · Cited by 978 · see citing works
Submodular functions and convexity
Lovász, L. (1983) · Springer eBooks · doi:10.1007/978-3-642-68874-4_10 · Cited by 968 · 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
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 · see citing works
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 · see citing works
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 · see citing works
Vertex packings: Structural properties and algorithms
Nemhauser, G. L., & Trotter, L. E. (1975) · Mathematical Programming · doi:10.1007/bf01580444 · Cited by 663 · see citing works
Stecke, K. E. (1983) · Management Science · doi:10.1287/mnsc.29.3.273 · Cited by 659 · see citing works
Cluster analysis and mathematical programming
Hansen, P., & Jaumard, B. (1997) · Mathematical Programming · doi:10.1007/bf02614317 · Cited by 653 · see citing works
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 · see citing works
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 · see citing works
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 · 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
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 · see citing works
Balas, E., & Padberg, M. W. (1976) · SIAM Review · doi:10.1137/1018115 · Cited by 452 · see citing works
Solvable spin systems with random interactions
Mattis, D. C. (1976) · Physics Letters A · doi:10.1016/0375-9601(76)90396-0 · Cited by 415 · see citing works
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 · see citing works
Cluster Analysis and Mathematical Programming
Rao, M. R. (1971) · Journal of the American Statistical Association · doi:10.1080/01621459.1971.10482319 · Cited by 377 · see citing works
Barahona, F., & Mahjoub, A. R. (1986) · Mathematical Programming · doi:10.1007/bf02592023 · Cited by 374 · see citing works
Algorithms for the maximum satisfiability problem
Hansen, P., & Jaumard, B. (1990) · Computing · doi:10.1007/bf02241270 · Cited by 362 · see citing works
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 · see citing works
The boolean quadric polytope: Some characteristics, facets and relatives
Padberg, M. W. (1989) · Mathematical Programming · doi:10.1007/bf01589101 · Cited by 356 · see citing works
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 332 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Minimum cuts and related problems
Picard, J., & Ratliff, H. D. (1975) · Networks · doi:10.1002/net.3230050405 · Cited by 246 · see citing works
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 · see citing works
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 · see citing works
Methods of Nonlinear 0-1 Programming
Hansen, P. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70343-1 · Cited by 222 · see citing works
Watters, L. J. (1967) · Operations Research · doi:10.1287/opre.15.6.1171 · Cited by 220 · see citing works
Franklin, J. (1980) · Undergraduate texts in mathematics · doi:10.1007/978-1-4613-9447-1_2 · Cited by 206 · see citing works
On the Approximation of Maximum Satisfiability
Yannakakis, M. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1045 · Cited by 201 · see citing works
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 · see citing works
Balas, E., & Padberg, M. W. (1972) · Operations Research · doi:10.1287/opre.20.6.1152 · Cited by 169 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Glover, F., & Woolsey, E. (1973) · Operations Research · doi:10.1287/opre.21.1.156 · Cited by 130 · see citing works
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 · see citing works
The Evaluation of Risky Interrelated Investments
Beckmann, M. J., & Hillier, F. S. (1973) · International Statistical Review · doi:10.2307/1402636 · Cited by 118 · see citing works
Nonlinear 0–1 programming: I. Linearization techniques
Balas, E., & Mazzola, J. B. (1984) · Mathematical Programming · doi:10.1007/bf02591796 · Cited by 115 · see citing works
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 · see citing works
Self-citationConstrained Nonlinear 0-1 Programming
Hansen, P., Jaumard, B., & Mathon (1989) · Les Cahiers du GERAD · Cited by 101 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Complexity of Partial Satisfaction
Lieberherr, K. J., & Specker, E. P. (1981) · Journal of the ACM · doi:10.1145/322248.322260 · Cited by 73 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Nonlinear 0–1 programming: II. Dominance relations and algorithms
Balas, E., & Mazzola, J. B. (1984) · Mathematical Programming · doi:10.1007/bf02591797 · Cited by 66 · see citing works
Billionnet, A., & Minoux, M. (1985) · Discrete Applied Mathematics · doi:10.1016/0166-218x(85)90035-6 · Cited by 65 · see citing works
Concave extensions for nonlinear 0–1 maximization problems
Crama, Y. (1993) · Mathematical Programming · doi:10.1007/bf01582138 · Cited by 65 · see citing works
Badics, T., & Boros, E. (1998) · Mathematics of Operations Research · doi:10.1287/moor.23.3.649 · Cited by 64 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Self-citationDeza, M. M., & Laurent, M. (1992) · Mathematical Programming · doi:10.1007/bf01580897 · Cited by 58 · see citing works
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 · see citing works
Self-citationRecognition problems for special classes of polynomials in 0–1 variables
Crama, Y. (1989) · Mathematical Programming · doi:10.1007/bf01587085 · Cited by 53 · see citing works
On the supermodular knapsack problem
Gallo, G., & Simeone, B. (1989) · Mathematical Programming · doi:10.1007/bf01589108 · Cited by 52 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
(0, 1) hyperbolic programming problems
Robillard, P. N. (1971) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800180104 · Cited by 45 · see citing works
Facets for the cut cone II: Clique-web inequalities
Deza, M. M., & Laurent, M. (1992) · Mathematical Programming · doi:10.1007/bf01580898 · Cited by 41 · see citing works
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 · see citing works
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 · see citing works
Hansen, P., & Simeone, B. (1986) · Discrete Applied Mathematics · doi:10.1016/0166-218x(86)90031-4 · Cited by 35 · see citing works
Adams, W. P., & Dearing, P. M. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(92)00119-7 · Cited by 34 · see citing works
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 · see citing works
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 · see citing works
Self-citationRoof duality for polynomial 0–1 optimization
Lu, S. H., & Williams, A. C. (1987) · Mathematical Programming · doi:10.1007/bf02591742 · Cited by 29 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
A strongly polynomial-time algorithm for minimizing submodular functions
Iwata, S., Fleischer, L., & Fujishige, S. (1999) · Cited by 24 · see citing works
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 · see citing works
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 · see citing works
Self-citationCombinatorial mathematics: Proceedings of the Third International Conference
Bloom, G. S., Graham, R., & Malkevitch, J. (1989) · Medical Entomology and Zoology · Cited by 23 · see citing works
Approximation algorithms for the maximum satisfiability problem
Asano, T., Ono, T., & Hirata, T. (1996) · Nordic journal of computing · Cited by 21 · see citing works
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 · see citing works
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 · see citing works
Self-citationQuadratic functions of binary variables
Hammer, P. L., & Simeone, B. (1989) · Lecture notes in mathematics · doi:10.1007/bfb0083461 · Cited by 20 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Self-citationPersistency in quadratic 0–1 optimization
Billionnet, A., & Sutter, A. (1992) · Mathematical Programming · doi:10.1007/bf01586044 · Cited by 16 · see citing works
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 · see citing works
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 · see citing works
Self-citationMaximum renamable Horn sub-CNFs
Boros, E. (1999) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(99)00031-1 · Cited by 14 · see citing works
Self-citationPseudo-Boolean Solutions to Multidimensional Location Problems
Warszawski, A. (1974) · Operations Research · doi:10.1287/opre.22.5.1081 · Cited by 14 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Young, A. P. (1984) · Journal of Statistical Physics · doi:10.1007/bf01009446 · Cited by 12 · see citing works
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 · see citing works
Self-citationCrama, Y., & Mazzola, J. B. (1995) · Annals of Operations Research · doi:10.1007/bf02032163 · Cited by 11 · see citing works
Average Performance of Heuristics for Satisfiability
Kohli, R., & Krishnamurti, R. (1989) · SIAM Journal on Discrete Mathematics · doi:10.1137/0402046 · Cited by 10 · see citing works
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 · see citing works
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 · see citing works
Self-citationGadgets, Approximation, and Linear Programming (extended abstract).
Trevisan, L., Sorkin, G. B., Sudan, M., & Williamson, D. P. (1996) · Cited by 8 · see citing works
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 · see citing works
Self-citationSimeone, B., & estivo, C. I. M. (1989) · Lecture notes in mathematics · doi:10.1007/bfb0083460 · Cited by 7 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Quelques utilisations de la struction
Hertz, A. (1986) · Discrete Mathematics · doi:10.1016/0012-365x(86)90071-3 · Cited by 6 · see citing works
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 · see citing works
Self-citationBimatroidal independence systems
Crama, Y., & Hammer, P. L. (1989) · Mathematical Methods of Operations Research · doi:10.1007/bf01423645 · Cited by 5 · see citing works
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 · see citing works
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 · see citing works
Sur la résolution des programmes fractionnaires en variables 0-1
Nagih, A. (1996) · Cited by 3 · see citing works
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 · see citing works
Flagged first, then by citations
3 of the 162 references couldn’t be matched to a known paper.
Research works printed but not linked: 6
- T. Badics, Approximation of some Nonlinear Binary Optimization Problems, Ph.D. Thesis, RUTCOR, Rutgers University, 1996.
- P. Hansen, B. Simeone, A class of quadratic pseudoboolean functions whose maximization is reducible to a network ow problem, CORR 79-39, Department of Comb. Optim., University of Waterloo.
- G. Owen, Game Theory, Academic Press, New York, 1982.
- 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.
- D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
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,063 · see citing works
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · see citing works
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 1,842 · see citing works
Learning to Discover Social Circles in Ego Networks
Leskovec, J., & McAuley, J. (2012) · neural information processing systems · Cited by 1,701 · 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
Determinantal Point Processes for Machine Learning
Kulesza, A., & Taskar, B. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000044 · Cited by 640 · see citing works
Non-convex mixed-integer nonlinear programming: A survey
Burer, S., & Letchford, A. N. (2012) · Surveys in Operations Research and Management Science · doi:10.1016/j.sorms.2012.08.001 · Cited by 544 · see citing works
Determinantal Point Processes for Machine Learning
Kulesza, A. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986290 · Cited by 493 · see citing works
The unconstrained binary quadratic programming problem: a survey
Kochenberger, G. A., Hao, J., Glover, F., Lewis, M. W., Lü, Z., Wang, H., & Wang, Y. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9734-0 · Cited by 479 · 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
Nikos Komodakis, A., & Pesquet, J.-C. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2377273 · Cited by 420 · see citing works
Fast approximate energy minimization with label costs
Delong, A., Osokin, A., Isack, H. N., & Boykov, Y. Y. (2010) · 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.2010.5539897 · Cited by 409 · see citing works
Feature Correspondence Via Graph Matching: Models and Global Optimization
Torresani, L., Kolmogorov, V., & Rother, C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88688-4_44 · Cited by 392 · see citing works
Fast Approximate Energy Minimization with Label Costs
Delong, A., Osokin, A., Isack, H. N., & Boykov, Y. Y. (2011) · International Journal of Computer Vision · doi:10.1007/s11263-011-0437-z · Cited by 383 · see citing works
Discovering social circles in ego networks
McAuley, J., & Leskovec, J. (2014) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2556612 · Cited by 367 · 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
Coupled Object Detection and Tracking from Static Cameras and Moving Vehicles
Leibe, B., Schindler, K., Cornelis, N., & Gool, L. V. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.170 · Cited by 354 · see citing works
Minor-embedding in adiabatic quantum computation: I. The parameter setting problem
Choi, V. (2008) · Quantum Information Processing · doi:10.1007/s11128-008-0082-9 · Cited by 410 · see citing works
A Linear Programming Approach to Max-Sum Problem: A Review
Werner, T. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1036 · Cited by 339 · see citing works
Semantic Labeling of 3D Point Clouds for Indoor Scenes
Koppula, H. S., Anand, A., Joachims, T., & Saxena, A. (2011) · neural information processing systems · Cited by 322 · see citing works
Quantum bridge analytics I: a tutorial on formulating and using QUBO models
Glover, F., Kochenberger, G. A., Hennig, R., & Du, Y. (2022) · Annals of Operations Research · doi:10.1007/s10479-022-04634-2 · Cited by 318 · see citing works
Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models
Glover, F., Kochenberger, G., & Du, Y. (2019) · 4OR · doi:10.1007/s10288-019-00424-y · Cited by 298 · see citing works
Learning with Submodular Functions: A Convex Optimization Perspective
Bach, F. (2013) · now publishers, Inc. eBooks · doi:10.1561/9781601987570 · Cited by 293 · see citing works
Training structural SVMs when exact inference is intractable
Finley, T., & Joachims, T. (2008) · International Conference on Machine Learning · doi:10.1145/1390156.1390195 · Cited by 260 · see citing works
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
Choi, V. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0200-3 · Cited by 278 · see citing works
Cheng, D. (2014) · Automatica · doi:10.1016/j.automatica.2014.05.005 · Cited by 244 · see citing works
Learning CRFs Using Graph Cuts
Szummer, M., Kohli, P., & Hoiem, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88688-4_43 · Cited by 243 · see citing works
A study on continuous max-flow and min-cut approaches
Yuan, J., Bae, E., & Tai, X.-C. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539903 · Cited by 237 · see citing works
A practical heuristic for finding graph minorsPreprint
Cai, J. L., Macready, W. G., & Roy, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.2741 · Cited by 284 · see citing works
P3 & Beyond: Solving Energies with Higher Order Cliques
Kohli, P., Kumar, M., & Torr, P. H. S. (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.383204 · Cited by 223 · see citing works
A case study in programming a quantum annealer for hard operational planning problems
Rieffel, E. G., Venturelli, D., O’Gorman, B., Do, M. B., Prystay, E. M., & Smelyanskiy, V. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0892-x · Cited by 221 · see citing works
Learning with Submodular Functions: A Convex Optimization Perspective
Bach, F. (2013) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000039 · Cited by 227 · see citing works
Wang, C., Nikos Komodakis, A., & Nikos Paragios, A. (2013) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2013.07.004 · Cited by 210 · see citing works
Fusion Moves for Markov Random Field Optimization
Lempitsky, V., Rother, C., Roth, S., & Blake, A. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.143 · Cited by 199 · see citing works
Dynamic Graph Cuts for Efficient Inference in Markov Random Fields
Kohli, P., & Torr, P. H. S. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1128 · Cited by 191 · see citing works
An Overview and Comparison of Smooth Labeling Methods for Land-Cover Classification
Schindler, K. (2012) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2012.2192741 · Cited by 187 · see citing works
Dynamic Programming and Graph Algorithms in Computer Vision
Felzenszwalb, P. F., & Ramin Zabih, A. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.135 · Cited by 184 · see citing works
Track to the future: Spatio-temporal video segmentation with long-range motion cues
Lezama, J., Alahari, K., Šivic, J., & Ivan Laptev, A. (2011) · doi:10.1109/cvpr.2011.6044588 · Cited by 185 · see citing works
Contextually guided semantic labeling and search for three-dimensional point clouds
Anand, A., Koppula, H. S., Joachims, T., & Saxena, A. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364912461538 · Cited by 216 · see citing works
Semantic segmentation of urban scenes by learning local class interactions
Volpi, M., & Ferrari, V. (2015) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw.2015.7301377 · Cited by 184 · see citing works
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem
Billionnet, A., & Elloumi, S. (2006) · Mathematical Programming · doi:10.1007/s10107-005-0637-9 · Cited by 182 · see citing works
Quantum Annealing for Prime Factorization
Jiang, S., Britt, K. A., McCaskey, A., Humble, T. S., & Kais, S. (2018) · Scientific Reports · doi:10.1038/s41598-018-36058-z · Cited by 179 · see citing works
Half-integrality based algorithms for cosegmentation of images
Mukherjee, L., Singh, V., & Dyer, C. R. (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.5206652 · Cited by 172 · see citing works
What metrics can be approximated by geo-cuts, or global optimization of length/area and flux
Kolmogorov, V., & Boykov, Y. Y. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.252 · Cited by 169 · see citing works
Image Labeling on a Network: Using Social-Network Metadata for Image Classification
McAuley, J., & Leskovec, J. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33765-9_59 · Cited by 167 · see citing works
Concise integer linear programming formulations for dependency parsing
Martins, A. F. T., Smith, N. A., & Xing, E. P. (2009) · doi:10.3115/1687878.1687928 · Cited by 166 · 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
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
On Total Variation Minimization and Surface Evolution Using Parametric Maximum Flows
Chambolle, A., & Darbon, J. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-009-0238-9 · Cited by 158 · see citing works
New Inference Rules for Max-SAT
Li, C., Manyà, F., & Planes, J. (2007) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2215 · Cited by 157 · see citing works
Dense non-rigid surface registration using high-order graph matching
Zeng, Y., Wang, C., Wang, Y., Gu, X. D., Samaras, D., & Nikos Paragios, A. (2010) · 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.2010.5540189 · Cited by 151 · see citing works
Object Detection and Tracking for Autonomous Navigation in Dynamic Environments
Ess, A., Schindler, K., Leibe, B., & Van Gool, L. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364910365417 · Cited by 191 · 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
Cosegmentation Revisited: Models and Optimization
Vicente, S., Kolmogorov, V., & Rother, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15552-9_34 · Cited by 145 · see citing works
Soft arc consistency revisited
Cooper, M., de Givry, S., Sánchez-Fibla, M., Schiex, T., Zytnicki, M., & Werner, T. (2010) · Artificial Intelligence · doi:10.1016/j.artint.2010.02.001 · Cited by 144 · see citing works
Nonlinear Integer ProgrammingPreprint
Hemmecke, R., Köppe, M., Lee, J., & Weismantel, R. (2009) · Cited by 152 · see citing works
Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)
Boros, E., Hammer, P. L., & Tavares, G. (2007) · Journal of Heuristics · doi:10.1007/s10732-007-9009-3 · Cited by 142 · see citing works
Self-citationSimpleFlow: A Non‐iterative, Sublinear Optical Flow Algorithm
Tao, M. W., Bai, J., Kohli, P., & Paris, S. (2012) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2012.03013.x · Cited by 139 · see citing works
Pylon Model for Semantic Segmentation
Lempitsky, V., Vedaldi, A., & Zisserman, A. (2011) · Cited by 129 · see citing works
Efficiently selecting regions for scene understanding
Kumar, M., & Koller, D. (2010) · 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.2010.5540072 · Cited by 128 · see citing works
Higher-order clique reduction in binary graph cut
Ishikawa, H. (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.5206689 · Cited by 128 · see citing works
The complexity of soft constraint satisfaction
Cohen, D. A., Cooper, M., Jeavons, P., & Krokhin, A. (2006) · Artificial Intelligence · doi:10.1016/j.artint.2006.04.002 · Cited by 127 · see citing works
Globally optimal segmentation of multi-region objects
Delong, A., & Boykov, Y. Y. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459263 · Cited by 126 · see citing works
A unified modeling and solution framework for combinatorial optimization problems
Kochenberger, G. A., Glover, F., Alidaee, B., & Rego, C. (2004) · OR Spectrum · doi:10.1007/s00291-003-0153-3 · Cited by 125 · see citing works
Perdomo, A., Truncik, C., Tubert-Brohman, I., Rose, G., & Aspuru-Guzik, A. (2008) · Physical Review A · doi:10.1103/physreva.78.012320 · Cited by 120 · see citing works
Scale invariant cosegmentation for image groups
Mukherjee, L., Singh, V., & Peng, J. (2011) · 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.2011.5995420 · Cited by 121 · see citing works
Biamonte, J. (2008) · Physical Review A · doi:10.1103/physreva.77.052331 · Cited by 118 · see citing works
FusionFlow: Discrete-continuous optimization for optical flow estimation
Lempitsky, V., Roth, S., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587751 · Cited by 145 · see citing works
Introduction to the mathematics of ambiguity
Massimo Marinacci, B., & Montrucchio, L. (2010) · Taylor & Francis eBooks · doi:10.4324/9780203358061_chapter_4 · Cited by 110 · see citing works
Genetic algorithm-based multi-criteria project portfolio selection
Yu, L., Wang, S., Wen, F., & Lai, K. K. (2010) · Annals of Operations Research · doi:10.1007/s10479-010-0819-6 · Cited by 109 · see citing works
Hemmecke, R., Köppe, M., Lee, J., & Weismantel, R. (2009) · Springer eBooks · doi:10.1007/978-3-540-68279-0_15 · Cited by 106 · see citing works
Video Pop-up: Monocular 3D Reconstruction of Dynamic Scenes
Russell, C., Yu, R., & Agapito, L. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10584-0_38 · Cited by 94 · 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
Learning to Estimate and Remove Non-uniform Image Blur
Couzinié-Devy, F., Sun, J. Z., Alahari, K., & Ponce, J. (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.143 · Cited by 101 · see citing works
Adiabatic quantum programming: minor embedding with hard faults
Klymko, C., Sullivan, B. D., & Humble, T. S. (2014) · Quantum Information Processing · doi:10.1007/s11128-013-0683-9 · Cited by 99 · see citing works
“, substituting the product of two variables with a ne w one and adding a corresponding penalty term [8].”
MethodGlobally Optimal Multi-target Tracking on a Hexagonal Lattice
Andriyenko, A., & Schindler, K. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15549-9_34 · Cited by 98 · see citing works
On the optimality of tree-reweighted max-product message-passingPreprint
Kolmogorov, V., & Wainwright, M. J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1395 · Cited by 98 · see citing works
Mathematical optimization ideas for biodiversity conservation
Billionnet, A. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.03.025 · Cited by 97 · see citing works
TRANSFORMING AN ARBITRARY MINSUM PROBLEM INTO A BINARY ONE
Schlesinger, D., & Flach, B. (2006) · Cited by 96 · see citing works
A Dual Decomposition Approach to Feature Correspondence
Torresani, L., Kolmogorov, V., & Rother, C. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.105 · Cited by 95 · 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
Self-citationExact inference in multi-label CRFs with higher order cliques
Ramalingam, S., Kohli, P., Alahari, K., & Torr, P. H. S. (2008) · 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.2008.4587401 · Cited by 88 · see citing works
Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis
Bian, Z., Chudak, F. A., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2016) · Frontiers in ICT · doi:10.3389/fict.2016.00014 · Cited by 86 · see citing works
On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing
Hadfield, S. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3478519 · Cited by 86 · see citing works
Interacting Tracklets for Multi-Object Tracking
Lan, L., Wang, X., Zhang, S. S., Tao, D., Gao, W., & Huang, T. S. (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2843129 · Cited by 86 · see citing works
Energy based multiple model fitting for non-rigid structure from motion
Russell, C., Fayad, J. K., & Agapito, L. (2011) · 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.2011.5995383 · Cited by 83 · see citing works
Partition Crossover for Pseudo-Boolean Optimization
Tinós, R., Whitley, D., & Chicano, F. (2015) · doi:10.1145/2725494.2725497 · Cited by 82 · see citing works
Iyer, R., & Bilmes, J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.0560 · Cited by 81 · 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
Self-citationFactoring larger integers with fewer qubits via quantum annealing with optimized parameters
Peng, W., Wang, B., Hu, F., Wang, Y.-J., Fang, X., Chen, X., & Wang, C. (2019) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-018-9307-1 · Cited by 76 · see citing works
Fixation probabilities in evolutionary dynamics under weak selection
McAvoy, A., & Allen, B. (2021) · Journal of Mathematical Biology · doi:10.1007/s00285-021-01568-4 · Cited by 72 · 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
Image Segmentation by Branch-and-Mincut
Lempitsky, V., Blake, A., & Rother, C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88693-8_2 · Cited by 71 · see citing works
On partial optimality in multi-label MRFs
Kohli, P., Shekhovtsov, A., Rother, C., Kolmogorov, V., & Torr, P. H. S. (2008) · International Conference on Machine Learning · doi:10.1145/1390156.1390217 · Cited by 67 · see citing works
Max-Margin Weight Learning for Markov Logic Networks
Huynh, T. N., & Mooney, R. J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04180-8_54 · Cited by 68 · see citing works
Preprocessing of unconstrained quadratic binary optimization
Boros, E., Hammer, P. L., & Tavares, G. (2006) · Cited by 66 · see citing works
Self-citationPrime factorization algorithm based on parameter optimization of Ising model
Wang, B., Hu, F., Yao, H., & Wang, C. (2020) · Scientific Reports · doi:10.1038/s41598-020-62802-5 · Cited by 69 · see citing works
Approximate inference in graphical models using lp relaxations
Jaakkola, T., & Sontag, D. A. (2010) · Cited by 61 · see citing works
Measuring uncertainty in graph cut solutions
Kohli, P., & Torr, P. H. S. (2008) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2008.07.002 · Cited by 62 · see citing works
Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT)
Whitley, L. D., Chicano, F., & Goldman, B. W. (2016) · Evolutionary Computation · doi:10.1162/evco_a_00184 · Cited by 62 · see citing works
- 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
