Content deleted Content added
No edit summary |
No edit summary |
||
Line 5:
An important class of pseudo-Boolean functions are the [[supermodular function|submodular functions]], because polynomimal-time algorithms exists for minimizing them. The '''degree''' of the pseudo-Boolean function is simply the degree of the polynomial.
In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function <math>f</math> that maps <math>\{-1,1\}^n</math> to <math>\mathbf{R}</math>. Again in this case we can uniquely write <math>f</math> as a multi-linear polynomial:
<math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, </math> where <math> \hat{f}(I) </math> are Fourier coefficients of <math>f</math> and <math>[n]=\{1,...,n\}</math>. For a nice and simple introduction to Fourier analysis of pseudo-Boolean functions, see <ref name="odon">O'Donnell, 2008</ref>.
==Optimization==
Line 28 ⟶ 29:
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>).
===Polynomial Compression Algorithms===
Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbf{R}</math>. Then <math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i. </math> Assume that each coefficient <math>\hat{f}(I)</math> is integral.
Then for an integer <math> k </math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math> k </math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref> that
in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k) </math>.
Let <math> r </math> be the degree of the above multi-linear polynomial for <math> f </math>. Then <ref name="crow">Crowston et al., 2011</ref> proved that in polynomial time we can either solve P or reduce the number of variables to <math> r(k-1) </math>.
| |||