Scientific Research and Development
Not only do we teach computer science, we push the boundaries of knowledge forward
How to recognize a good faculty? It does top science. Just like we do at FI.
What is our recipe for premium results?
Lectures, Informatics Colloquia, and News
19 NovRead moreInformatics 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.
"I'd like to thank our academics and students, particularly our doctoral students, for publishing work that has seen the Faculty of Informatics ranked first out of 55 institutions in the area in disciplinary comparisons published by IDEA CERGE in Oborová publikační výkonnost pracovišť výzkumných organizací v ČR v letech 2009-2013.Prof. Jiří Zlatuška
FI MU Dean