Location: MF 14

Speaker: Kristýna Pekárková (Masaryk University)

Title: Matroid-based approach to matrix sparsification

Abstract:
Recent research in the area of combinatorial optimization and parameterized complexity shows that integer programming is tractable when the input instance has a certain block structure or the constraint matrix is sparse. However, most existing IP algorithms require the constraint matrix to already be in a block-like or sparse form. This is a substantial drawback, as existing algorithms cannot be applied to instances that are not sparse themselves, but can be transformed to an equivalent sparse instance. In this talk, we will explain how structural properties of matroids can be applied in the context of integer programming, with a particular focus on matrices of bounded tree-depth. 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.

The talk is based on joint work with M. Briański, T. Chan, J. Cooper, M. Koutecký, D. Kráľ, and F. Schröder.