Combinatorial Optimization Reading Group - Matt Gerstbrein

Friday, March 6, 2020 1:00 pm - 1:00 pm EST (GMT -05:00)

Title: Recognizing slack matrices

Speaker: Matt Gerstbrein
Affiliation: University of Waterloo
Room: MC 5417


This week, we will be discussing the topic of slack matrices. Slack matrices arise in the context of lifts of polytopes, where, given a polytope P, we can characterize the existence of a lift of P of a given size in terms of properties of an associated slack matrix. In this talk, we will discuss the problem of determining whether a given non-negative matrix is a slack matrix of some polytope (or cone). We will provide a characterization of such matrices, and will also discuss some related algorithmic results.