Pseudo-Boolean function: Difference between revisions

Revision as of 09:49, 8 July 2023

Revision as of 10:41, 8 July 2023

Line 14:

==Optimization==

Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is [[NP-hard]]. This can easily be seen by formulating, for example, the [[maximum cut]] problem as maximizing a pseudo-Boolean function.<ref name=boroshammerBoros2002/>

===Submodularity===

Line 23:

===Roof Duality===

If ''f'' is a quadratic polynomial, a concept called ''roof duality'' can be used to obtain a lower bound for its minimum value.<ref name=boroshammerBoros2002>{{cite journal |last1=Boros and|first1=E. |last2=Hammer, |first2=P. L. |year=2002 |title=Pseudo-Boolean Optimization |journal=[[Discrete Applied Mathematics]] |doi=10.1016/S0166-218X(01)00341-9 |doi-access=free |volume=123 |issue=1–3 |pages=155–225 |url=http://orbi.ulg.ac.be/handle/2268/202427}}</ref> Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.<ref name=boroshammerBoros2002/>

===Quadratizations===

Line 45:

==References==

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

* {{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}}