CoChat
Sign Up
PreprintCited by 32Advanced Optimization Algorithms ResearchComplexity and Algorithms in GraphsPolynomial and algebraic computation

On Quadratization of Pseudo-Boolean Functions

Open access
Boros, Endre, Gruber, Aritanan·2014·arXiv
DOI 10.48550/arxiv.1404.6538arXiv 1404.6538
Open this paper in CoChat — free accountOpen PDF

Abstract

We survey current term-wise techniques for quadratizing high-degree pseudo-Boolean functions and introduce a new one, which allows multiple splits of terms. We also introduce the first aggregative approach, which splits a collection of terms based on their common parts.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1404.6538

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.

A few free checks a day · papers already verified open instantly · results are public

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 [167]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 23 · Cited by 32

Research works printed but not linked: 24

  1. [1][1] Billionnet, A., and Minoux, M. Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. Discrete Applied Mathematics 12 , 1 (1985), 1 - 11. -
  2. [4][4] Boros, E., Hammer, P. L., Sun, R., and Tavares, G. A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optimization 5 , 2 (2008), 501-529. -
  3. [5][5] Buchheim, C., and Rinaldi, G. Efficient reduction of polynomial zero-one optimization to the quadratic case. SIAM Journal on Optimization 18 , 4 (2007), 1398-1413. -
  4. [6][6] Crama, Y. Recognition problems for special classes of polynomials in 0 -1 variables. Mathematical Programming 44 (1989), 139-155. 10.1007/BF01587085. - · DOI
  5. [7][7] Fix, A., Gruber, A., Boros, E., and Zabih, R. A graph cut algorithm for higher-order markov random fields. In ICCV (2011), D. N. Metaxas, L. Quan, A. Sanfeliu, and L. J. V. Gool, Eds., IEEE, pp. 1020-1027. -
  6. [8][8] Freedman, D., and Drineas, P. Energy minimization via graph cuts: Settling what is possible. In CVPR (2) (2005), IEEE Computer Society, pp. 939-946. -
  7. [9][9] Gallo, G., and Simeone, B. On the supermodular knapsack problem. Mathematical Programming 45 (1989), 295-309. -
  8. [10][10] Gr¨ otschel, M., Lov´ asz, L., and Schrijver, A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 , 2 (1981), 169-197. -
  9. [11][11] Hammer, P., Hansen, P., and Simeone, B. Roof duality, complementation and persistency in quadratic 0 -1 optimization. Mathematical Programming 28 (1984), 121-155. -
  10. [12][12] Hammer, P., and Rudeanu, S. Boolean Methods in Operations Research and Related Areas . Springer Verlag, 1968. -
  11. [13][13] Hammer, P. L. Some network flow problems solved with pseudo-boolean programming. Operations Research 13 , 3 (1965), 388-399. -
  12. [14][14] Hansen, P. Methods of nonlinear 0 -1 programming. Annals of Discrete Mathematics 5 (1979), 53-70. -
  13. [15][15] Ishikawa, H. Higher-order gradient descent by fusion-move graph cut. In ICCV (2009), IEEE, pp. 568-574. -
  14. [16][16] Ishikawa, H. Transformation of general binary MRF minimization to the first-order case. IEEE Trans. Pattern Anal. Mach. Intell. 33 , 6 (2011), 1234-1249. -
  15. [17][17] Iwata, S., Fleischer, L., and Fujishige, S. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. In STOC (2000), pp. 97-106. -
  16. [18][18] Kolmogorov, V., and Zabih, R. What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26 , 2 (2004), 147-159. -
  17. [19][19] Ramalingam, S., Russell, C., Ladicky, L., and Torr, P. H. S. Efficient minimization of higher order submodular functions using monotonic boolean functions. CoRR abs/1109.2304 (2011). - · arXiv
  18. [21][21] Roth, S., and Black, M. J. Fields of experts. International Journal of Computer Vision 82 , 2 (2009), 205-229. -
  19. [22][22] Rother, C., Kohli, P., Feng, W., and Jia, J. Minimizing sparse higher order energy functions of discrete variables. In CVPR (2009), IEEE, pp. 1382-1389. -
  20. [23][23] Rother, C., Kolmogorov, V., Lempitsky, V. S., and Szummer, M. Optimizing binary MRFs via extended roof duality. In CVPR (2007), IEEE Computer Society. -
  21. [24][24] Schrijver, A. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory, Ser. B 80 , 2 (2000), 346-355. -
  22. [25][25] Zivny, S., Cohen, D. A., and Jeavons, P. G. The expressive power of binary submodular functions. Discrete Applied Mathematics 157 , 15 (2009), 3347-3358. -
  23. [26][26] Zivny, S., Cohen, D. A., and Jeavons, P. G. The expressive power of binary submodular functions. In MFCS (2009), R. Kr´ alovic and D. Niwinski, Eds., vol. 5734 of Lecture Notes in Computer Science , Springer, pp. 744-757. -
  24. [27][27] Zivny, S., and Jeavons, P. G. Classes of submodular constraints expressible by graph cuts. Constraints 15 , 3 (2010), 430-452.

Authors
Boros, E., & Gruber, A.
Affiliations
Rutgers, The State University of New Jersey (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2014
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1404.6538
arXiv
1404.6538
OpenAlex
W1633611286
Cited by
32
References
23
Citations by year
2026: 2 · 2025: 1 · 2024: 1 · 2023: 6 · 2021: 3 · 2020: 2 · 2019: 1 · 2018: 1 · 2017: 2 · 2016: 4 · 2015: 3 · 2014: 4 · 2012: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Polynomial and algebraic computation
Keywords
quadratization, pseudo-Boolean functions, term splitting, QUBO, 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