29 July 2017
Theory of pseudo-Boolean functions and binary optimization
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.
Endre Boros, MSIS and RUTCOR, Rutgers University, New Jersey, USA
Bring together PhD students and leading experts
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.