Extension Complexity.


A polytope Q is called an extension of a polytope P if P is a projection of Q. The extension complexity of a polytope is the minimum number of inequalities needed to describe any of its extensions. In this talk I will describe some results related to extension complexities of several important polytopes arising in combinatorial optimization and discuss how extension complexity can be used to model computational difficulty of solving problems.

Date: Sep 12, 2018 at 14:30 h
Venue: República 701, Sala 33 (3er piso).
Speaker: Hans Raj Tiwary
Affiliation: Charles U, Czech Republic.
Coordinator: Prof: Mario B.; Andrea J.; José V.
More info at:
Event website

Posted on Sep 10, 2018 in AGCO, Seminars