Rogla, Slovenia

Theory of pseudo-Boolean functions and binary optimization

when 23 July 2017 - 29 July 2017
language English
duration 1 week
credits 2 EC
fee EUR 150

Pseudo-Boolean functions are real valued mappings from the set of n-dimensional binary vectors, or equivalently from the power set of an n-element base set. Such mappings can be represented as multilinear polynomials in n-variables. Most graph and hypergraph parameters can be viewed as extremal values of such mappings. Pseudo-Boolean arise naturally in the formulations of most combinatorial optimization problems. In this course we will study the properties of pseudo-Boolean functions and their applications. The following is the tentative list of topics to be covered:

1) Properties of multilinear polynomials and posiform representations; examples for applications in graph theory and combinatorics; continuous extensions and relations to probability theory; the basic algorithm and clique width of co-occurance graphs.

2) Posiform maximization and graph stability; bi-clique covers of graphs; subcube-intersection graphs.

3) Linearization techniques; valid inequalities and facets of related polyhedra. Persistencies, autarkies and roof duality.

4) Quadratization techniques and their applications.

5) Special classes: submodular functions; quadratic functions; maximum-satisfiability problems and approximation algorithms.

Course leader

Endre Boros, MSIS and RUTCOR, Rutgers University, New Jersey, USA

Target group

PhD Students

Course aim

Bring together PhD students and leading experts

Fee info

EUR 150: Fee covers the social activities.


We have limited financial support for Phd-students. This includes half-board in one of the bungalows and the exemption from conference fee payment.

If you want to apply for it, please indicate it in the registration and send us a short CV.