Pseudo-Boolean function: Difference between revisions

Revision as of 18:46, 13 December 2019

Revision as of 20:31, 29 August 2020

Line 5:

==Representations==

Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Cite journal|url = |title = On the determination of the minima of pseudo-Boolean functions|lastlast1 = Hammer|firstfirst1 = P.L.|date = 1963|journal = Studii ¸si Cercetari Matematice|doi = |pmid = |access-date = |last2 = Rosenberg|first2 = I.|last3 = Rudeanu|first3 = S.|issue = 14|pages = 359–364|language = Romanian|issn = 0039-4068}}</ref><ref>{{Cite book|title = Boolean Methods in Operations Research and Related Areas|lastlast1 = Hammer|firstfirst1 = Peter L.|publisher = Springer|year = 1968|isbn = 978-3-642-85825-3|___location = |pages = |last2 = Rudeanu|first2 = Sergiu}}</ref>

:<math>f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i<j}a_{ij}x_ix_j + \sum_{i<j<k}a_{ijk}x_ix_jx_k + \ldots</math>

The '''degree''' of the pseudo-Boolean function is simply the degree of the [[polynomial]] in this representation.

Line 53:

==References==

* {{cite journal|author1=Boros, E.|author2=Hammer, P. L. |title=Pseudo-Boolean Optimization|journal= [[Discrete Applied Mathematics]] |year=2002|volume=123|issue=1–3 |pages=155–225 |doi=10.1016/S0166-218X(01)00341-9|url=http://orbi.ulg.ac.be/handle/2268/202427 }}

* {{cite journal|author1=Crowston, R. |author2=Fellows, M. | author3= Gutin, G. |author4=Jones, M. | author5= Rosamond, F. |author6=Thomasse, S. | author7= Yeo, A.|title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average.|journal=Proc. Of FSTTCS 2011|year=2011|arxiv=1104.1135|bibcode=2011arXiv1104.1135C}}

* {{cite journal|last=Ishikawa | first=H. |title=Transformation of general binary MRF minimization to the first order case|journal= [[IEEE Transactions on Pattern Analysis and Machine Intelligence]] |year=2011|volume=33|number=6|pages=1234–1249| doi=10.1109/tpami.2010.91|pmid=20421673|citeseerx=10.1.1.675.2183| s2cid=17314555 }}

* {{cite conference|author1=Kahl, F.|author2=Strandmark, P. |title=Generalized Roof Duality for Pseudo-Boolean Optimization| conference= [[International Conference on Computer Vision]] |year=2011|url=http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf}}

* {{cite journal|last=O'Donnell|first=Ryan|title=Some topics in analysis of Boolean functions|journal={{ECCC|2008|08|055}}|year=2008|url=http://www.eccc.uni-trier.de/eccc-reports/2008/TR08-055/}}