Informatické kolokvium 19.11. Matroid algorithms and integer programming
Informatické kolokvium 19.11. 2019, 14:00 posluchárna D2
prof. RNDr. Daniel Kráľ, Ph.D., DSc., FI MU
Matroid algorithms and integer programming
Abstrakt: 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.