Syllabus
1. Basic definitions and notation, examples of optimization problems which can be formulated as Pseudo-Boolean minimization or maximization.
2. Representations of Pseudo-Boolean functions (multi=linear polynomials, posiforms) and transformations between them.
3. Rounding, derandomization, local optima.
4. Reductions of general optimization to quadratic one.
5. Posiform maximization.
6. Applications to game theory.
7. Quadratic optimization and roof duality.
8. Persistency and the connection to network flows.
9. Generalizations of roof duality, hierarchy of bounds.
10. Aproximations.
11. Special classes.
Annotation
This course is suitable for all master and doctoral students who have acquired at least basic knowledge of mathematical logic, graph theory, network flows, and complexity of algorithms. The course covers several areas of interesting problems centerted around Pseudo-Boolean functions.
A particular emphasis will be given to applications of Pseudo-Boolean functions to solving hard optimization problems.