YouTube recording: https://www.youtube.com/watch?v=OaRpqCco8ko
Time: Thursday, Apr 13, 3pm ET
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 integer programming is, in general, NP-hard, and a long line of research has been devoted to identifying instances of IP that can be solved efficiently. In the talk, we will explain how structural properties of matroids can be applied in the context of integer programming. Our main focus is on matroid depth parameters, namely contraction*-depth and deletion-depth. In particular, we will discuss how these parameters can be used to design algorithms that efficiently transform the constraint matrix of an instance of integer programming into an equivalent sparse (and so computationally tractable) form.