Pseudo-Boolean function: Difference between revisions

Revision as of 21:30, 6 March 2024

Revision as of 06:22, 1 May 2024

Line 20:

:<math>f(\boldsymbol{x}) + f(\boldsymbol{y}) \ge f(\boldsymbol{x} \wedge \boldsymbol{y}) + f(\boldsymbol{x} \vee \boldsymbol{y}), \; \forall \boldsymbol{x}, \boldsymbol{y}\in \mathbf{B}^n\,.</math>

This is an important class of pseudo-boolean functions, because they can be [[Submodular set function#Submodular Minimizationset function minimization|minimized in polynomial time]]. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000).

===Roof Duality===