Can I read Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming on EtoBox?

Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming by Brianski, Marcin; Koutecky, Martin; Kral, Daniel; Pekarkova, Kristyna; Schroder, Felix is a scholarly article available to read on EtoBox.

What is Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming about?

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix $A$ and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of $A$, and when parameterized by the dual tree-depth and the entry complexity of $A$; both these parameterization imply that $A$ is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the $\ell_1$-norm of the Graver basis is bounded by a function of the maximum $\ell_1$-norm of a circuit of $A$. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix $A$ that has small primal/dual tree-depth and entry complexity if

Author

Brianski, Marcin; Koutecky, Martin; Kral, Daniel; Pekarkova, Kristyna; Schroder, Felix

Published

2022

Language

EN