Combinatorial Optimization Reading Group - Matt Gerstbrein

Title: Recognizing slack matrices

Abstract:

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.