To main content To navigation

Natural Sciences

Theory of pseudo-Boolean functions and binary optimization

When:

23 July - 29 July 2017

School:

PhD Summer School in Discrete Mathematics

Institution:

University of Primorska

City:

Rogla

Country:

Slovenia

Language:

English

Credits:

2.0 EC

Fee:

150 EUR

Interested?

About

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

Interested?

When:

23 July - 29 July 2017

School:

PhD Summer School in Discrete Mathematics

Institution:

University of Primorska

Language:

English

Credits:

2.0 EC

Fee:

150 EUR, Fee covers the social activities.

Visit school

Stay up-to-date about our summer schools!

If you don’t want to miss out on new summer school courses, subscribe to our monthly newsletter.