Formulating problems via linear inequalities and projections is at the heart of the polyhedral combinatorics approach to Combinatorial Optimization. We present some examples for which this can be achieved with surprisingly few inequalities and we give an almost pictorial proof showing that for other problems exponentially many inequalities are required.

Einladung von Prof. Nicole Megow