Spring School

A Spring School will be organized after the conference, on May 19-20 in the same venue. 

 

Downloads

Volker Kaibel:

Samuel Fiorini:

 

 

Important Dates

Extended early registration deadline for Spring SchoolApril 19, 2016

Early registration deadline for Spring School: April 12, 2016

Spring School: May 19-20, 2016

 

Title

Extended Formulations for Combinatorial Optimization  

 

Lecturers

 

Abstract

The topic of extended formulations, i.e., representing polyhedra or other geometric objects important for optimization as projections of higher dimensional geometric objects, has attracted a lot of attention over the last few years. In this spring school, we start with an introduction into the subject and then proceed to covering several aspects that are relevant to current research. The specific topics to be covered include methods of construction of extended formulations, lower bounds on their smallest possible sizes, connections to factorizations of slack matrices and communication complexity, and relations to hierarchies of relaxations such as the Sherali-Adams hierarchy.

 

Program

May 19 (morning), V. Kaibel

  • 8.30-10.30: Introduction with examples like, e.g., parity polytope, spanning trees in planar graphs
  • 11.00-13.00: Construction methods like disjunctions, dynamic programming, LP based separation

May 19 (afternoon), S. Fiorini

  • 14.30-16.30: Semidefinite extended formulations: theta bodies and theta rank; approximating Max Cut
  • 16.30-17.00: Coffee Break
  • 17.00-19.00: The Sherali-Adams (SA) hierarchy: definition(s); when SA performs well: stable sets in bounded treewidth graphs;  when SA performs poorly: Max Cut

May 20 (morning), V. Kaibel

  • 8.30-10.30: Slack matrices, factorization theorem, rectangle covering bound
  • 11.00-13.00: Easy lower bound for extended complexity of the correlation polytope

May 20 (afternoon), S. Fiorini

  • 14.30-16.30: Extended formulations as communication protocols: stable set polytopes of perfect graphs, extended formulations from circuits
  • 16.30-17.00: Coffee Break
  • 17.00-19.00: More lower-bounding techniques: reduction between problems, hyperplane separation, optimality of SA