Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 16, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Jerri Nummenpalo
Many problems in combinatorics can be formulated in terms of linear programs whose feasible regions are polytopes. Often, such polytopes are described by exponentially many linear inequalities. Extension complexity asks if there is a way to represent a given polytope in a higher dimensional space - a lifted polytope - so that fewer inequalities are needed. Yannakakis showed in the 90s a way to give lower bounds for the number of inequalities needed to describe any lifted polytope which maps linearly to the original polytope. Recently, new lower bounds on the extension complexity of interesting polytopes were attained. In this talk we introduce the concept of extension complexity of polytopes, look at ways to bound it and review some of these recent results.
Automatic MiSe System Software Version 1.4803M | admin login