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.
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.
Scholarships
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.
Deadline