YouTube recording: https://www.youtube.com/watch?v=OaRpqCco8ko
Time: Thursday, Apr 13, 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683
Speaker: Kristyna Pekárková, Masaryk University
Title: Matroid-based approach to matrix sparsification
Abstract: Integer programming (IP) is a fundamental problem of discrete optimization;its notable applications can be found, for example, in scheduling and planning,string algorithms, or computational social choice. Solving instances of integerprogramming is, in general, NP-hard, and a long line of research has beendevoted to identifying instances of IP that can be solved efficiently. In thetalk, we will explain how structural properties of matroids can be applied inthe context of integer programming. Our main focus is on matroid depthparameters, namely contraction*-depth and deletion-depth. In particular, wewill discuss how these parameters can be used to design algorithms thatefficiently transform the constraint matrix of an instance of integerprogramming into an equivalent sparse (and so computationally tractable)form.