Pseudo-Boolean function: Difference between revisions

Revision as of 14:21, 18 August 2011

Revision as of 14:26, 18 August 2011

Line 6:

==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.

===Submodularity===

A pseudo-Boolean function ''f'' is said to be '''submodular''' if

:<math> f(\boldsymbol{x}) + f(\boldsymbol{y}) \ge f(\boldsymbol{x} \wedge \boldsymbol{y}) + f(\boldsymbol{x} \vee \boldsymbol{y}) </math>

for every '''''x''''' and '''''y'''''. This is a very importand concept, because a submodular pseudo-boolean function can be minimized in polynomial time.{{citationCitation needed|date=August 2011}}

===Roof Duality===

Line 17:

===Reductions===

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,

:<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:

:<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>).