Pseudo-Boolean function: Difference between revisions

Revision as of 19:41, 12 September 2011

Revision as of 20:01, 12 September 2011

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 Fourier analysis of pseudo-Boolean functions, a pseudo-Boolean function is definedviewed 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>.

Line 27:

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

===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 of deciding whether <math> f(x)\geq k <\math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref>. that

in polynomial time we can either decide whether <math> f(x)\geq k <\math> or reduce the number of variables to <math> O(k^2\log k) </math>.

==See also==

Line 33 ⟶ 39:

==References==

* {{cite journal|last=Boros|coauthors=Hammer|title=Pseudo-Boolean Optimization|journal=Discrete Applied Mathematics|year=2002|volume=123|doi=10.1016/S0166-218X(01)00341-9}}

* {{cite journal|last=Crowston|coauthors=Fellows, Gutin, Jones, Rosamond, Thomasse, Yeo|title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average.|journal=Proc. of FSTTCS 2011|year=2011|url=http://arxiv.org/abs/1104.1135}}

* {{cite journal|last=Ishsikawa|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}}

Line 38 ⟶ 45:

TR08-055|year=2008|url=www.eccc.uni-trier.de/eccc-reports/2008/TR08-055/}}

R. , M. ,

Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average. Submitted. %%% to .

==Notes==

<references />