\contentsline {section}{\numberline {1}Introduction}{3}
\contentsline {section}{\numberline {2}Definitions and Notations}{4}
\contentsline {section}{\numberline {3}Examples}{6}
\contentsline {section}{\numberline {4}General Pseudo-Boolean Functions}{8}
\contentsline {subsection}{\numberline {4.1}Representations of pseudo-Boolean functions}{8}
\contentsline {subsection}{\numberline {4.2}Rounding procedures and derandomization}{10}
\contentsline {subsection}{\numberline {4.3}Local Optima}{13}
\contentsline {subsection}{\numberline {4.4}Reductions to Quadratic Optimization}{15}
\contentsline {subsection}{\numberline {4.5}Persistency}{19}
\contentsline {subsection}{\numberline {4.6}Basic Algorithm}{21}
\contentsline {subsection}{\numberline {4.7}Posiform Maximization}{24}
\contentsline {subsection}{\numberline {4.8}$l_2$-Approximations and Applications to Game Theory}{30}
\contentsline {section}{\numberline {5}Quadratic Pseudo-Boolean Functions}{35}
\contentsline {subsection}{\numberline {5.1}Roof Duality}{36}
\contentsline {subsubsection}{\numberline {5.1.1}Majorization}{36}
\contentsline {subsubsection}{\numberline {5.1.2}Linearization}{38}
\contentsline {subsubsection}{\numberline {5.1.3}Complementation}{39}
\contentsline {subsubsection}{\numberline {5.1.4}Equivalence of Formulations and Persistency}{40}
\contentsline {subsubsection}{\numberline {5.1.5}Network flow model}{43}
\contentsline {subsection}{\numberline {5.2}Hierarchy of Bounds}{48}
\contentsline {subsubsection}{\numberline {5.2.1}Cones of positive quadratic pseudo-Boolean functions}{48}
\contentsline {subsubsection}{\numberline {5.2.2}Complementation, Majorization, Linearization}{49}
\contentsline {subsection}{\numberline {5.3}Polyhedra}{53}
\contentsline {subsection}{\numberline {5.4}Heuristics}{55}
\contentsline {section}{\numberline {6}Special Classes}{58}
\contentsline {subsection}{\numberline {6.1}Sub- and supermodular functions}{58}
\contentsline {subsection}{\numberline {6.2}Half-products}{60}
\contentsline {subsection}{\numberline {6.3}Hyperbolic pseudo-Boolean programming}{61}
\contentsline {subsection}{\numberline {6.4}Products of linear functions}{63}
\contentsline {section}{\numberline {7}Approximation Algorithms}{64}
\contentsline {subsection}{\numberline {7.1}MAX-SAT and variants}{64}
\contentsline {subsection}{\numberline {7.2}$3/4$-approximation of MAX-2-SAT via roof-duality}{67}
\contentsline {subsection}{\numberline {7.3}$3/4$-approximation of MAXSAT via convex majorization}{69}