SFU Discrete Math Seminar: Timothy Chan

Integer programming is one of the most fundamental problems in discrete optimization. While integer programming is computationally hard in general, there exist efficient algorithms for special instances. In particular, integer programming is fixed parameter tractable when parameterized by the dual tree-depth of an input matrix and its entry complexity. However, the dual tree-depth of a matrix is not invariant under row-operations, i.e., it is possible that an input instance can be transformed to an instance with much smaller tree-depth. We use tools from matroid theory to address this problem. In particular, we will show that the branch-depth of the matroid formed by the columns of a matrix is equal to the minimum tree-depth of a row-equivalent matrix, and we design a fixed parameter algorithm for integer programming parameterized by the branch-depth of an input matrix and the entry complexity.

The talk is based joint work with Jacob Cooper, Martin Koutecky, Dan Kral, and Kristyna Pekarkova.