Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHAN Timothy Fong Nam COOPER Jacob KOUTECKÝ Martin KRÁĽ Daniel PEKÁRKOVÁ Kristýna

Year of publication 2020
Type Article in Proceedings
Conference Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), p. "26:1"-"26:19", 19 pp. 2020.
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.4230/LIPIcs.ICALP.2020.26
Keywords matroid algorithms; width parameters; integer programming; fixed parameter tractability; branch-width; branch-depth
Description A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry D are solvable in time g(d,D)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,D)poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info