Pseudo-Boolean function: Difference between revisions

Revision as of 18:13, 5 June 2025

Latest revision as of 04:13, 21 June 2025

Line 32:

Different reductions lead to different results. Take for example the following [[Cubic function|cubic polynomial]]:<ref name=Kahl2011>{{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}}</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−3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2−2 and the optimal assignment of every variable (which is <math> {(0,1,1)}</math>).

===Polynomial Compression Algorithms===