News and events archive

Informatics Colloquium 19.11. 2019, 14:00 lecture hall D2 prof. RNDr. Daniel Kráľ, Ph.D., DSc., FI MU Matroid algorithms and integer programming Abstract: While integer programming is computationally hard in general, efficient algorithms exist for various special instances. For example, there exists a fixed parameter algorithm for integer programs where the constraint matrix has bounded dual tree-depth and bounded entries. In this talk, we present a matroid based algorithm for finding an equivalent instance of an integer program where the constraint matrix has small dual tree-depth. The talk will start with a brief introduction to matroids and algorithmic problems concerning matroids. We will particularly focus on width parameters for matroids and algorithms for matroids with small width. One of the results that we will present asserts that the branch-depth of the matroid formed by columns of a matrix is equal to the minimum tree-depth of a row-equivalent matrix, and we will discuss algorithmic corollaries of this result in particular in relation to integer programming. The talk will be self-contained. The results presented in this talk are based on joint work with Timothy Chan, Jacob Cooper, Martin Koutecky and Kristyna Pekarkova.