Pseudo-Boolean function: Difference between revisions

Revision as of 10:41, 8 July 2023

Revision as of 10:43, 8 July 2023

Line 30:

There are other possibilities, for example,

:<math>\displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1.</math>

Different reductions lead to different results. Take for example the following cubic polynomial:<ref name=kahlstrandmarkKahl2011>{{cite conference |last1=Kahl and|first1=F. |last2=Strandmark, |first2=P. |year=2011|title=Generalized Roof Duality for Pseudo-Boolean Optimization |conference=[[International Conference on Computer Vision]] |url=http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf}}</ref>

:<math>\displaystyle f(\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3.</math>

Using the first reduction followed by roof duality, we obtain a lower bound of -3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is <math> {(0,1,1)}</math>).

Line 47:

* {{cite journal |last1=Crowston |first1=R. |last2=Fellows |first2=M. |last3=Gutin |first3=G. |last4=Jones |first4=M. |last5=Rosamond |first5=F. |last6=Thomasse |first6=S. |last7=Yeo |first7=A. |year=2011 |title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average. |journal=Proc. Of FSTTCS 2011 |arxiv=1104.1135 |bibcode=2011arXiv1104.1135C}}

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

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

* {{cite journal |last=O'Donnell |first=Ryan |year=2008 |title=Some topics in analysis of Boolean functions |journal=ECCC |issn=1433-8092 |url=https://eccc.weizmann.ac.il/report/2008/055/}}

* {{cite conference |last1=Rother |first1=C. |last2=Kolmogorov |first2=V. |last3=Lempitsky |first3=V. |last4=Szummer |first4=M. |year=2007 |title=Optimizing Binary MRFs via Extended Roof Duality |conference=[[Conference on Computer Vision and Pattern Recognition]] |url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}