***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Dan Kráľ (Masaryk University)
Thursday 14th September, 3:00 in Fine Hall 224.
Matroid depth parameters and preconditioners for integer programming
Dan Kráľ (Masaryk University)
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 primal or
dual tree-depth of the constraint matrix and its entry complexity. However,
constraint matrices describing the same instance of integer programming may have
differ tree-depth. We use tools from matroid theory to design efficient
algorithms that find an equivalent instance of smallest possible tree-depth.
Our main algorithm is based on the notion of contraction*-depth, which is the
matroid analogue of graph tree-depth. We start with introducing the notion and
other matroid width and depth parameters and survey their structural properties.
We then relate the contraction*-depth of the column matroid of a matrix to the
smallest tree-depth of a row-equivalent matrix, and exploit our structural
results to design algorithms of relevance in integer programming.
The talk is based on results jointly obtained with Marcin Briański, Jacob
Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková
and Felix Schröder.
----------------------------------
Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)