Content deleted Content added
Heavy Horse (talk | contribs) |
example is from this paper |
||
Line 23:
If the degree of ''f'' is greater than 2, one can always employ ''reductions'' to obtain an equivalent quadratic problem with additional variables.<ref name="ishikawa2011">Ishikawa, 2011</ref> One possible reduction is
:<math>\displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3)</math>
There are other possibilities, for example,<ref name="kahlstrandmark">Kahl and Strandmark, 2011</ref>
:<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:
Line 44:
* {{cite journal|last=Ishikawa|title=Transformation of general binary MRF minimization to the first order case|journal=IEEE Trans. Pattern Analysis and Machine Intelligence|year=2011|volume=33|number=6|pages=1234–1249}}
* {{cite journal|last=Rother|coauthors=Kolmogorov, Lempitsky, Szummer|title=Optimizing Binary MRFs via Extended Roof Duality|journal=International Conference on Computer Vision and Pattern Recognition|year=2007|url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}
* {{cite journal|last=Kahl|coauthors=Strandmark|title=Generalized Roof Duality for Pseudo-Boolean Optimization|journal=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|title=Some topics in analysis of Boolean functions|journal=ECCC Report
TR08-055|year=2008|url=http://www.eccc.uni-trier.de/eccc-reports/2008/TR08-055/}}
| |||