Online Talk: Kristyna Pekárková

YouTube recording:

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 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.