Dear all,
There will be a noon seminar this Thursday, 6 April, given by Kristýna Pekárková. Please find the talk details below.
Best regards, Misha Tyomkyn.
----------------------------------------------------
Preconditioners for matrix sparsity Kristýna Pekárková Masaryk University April 6, 2023, 12:20 in S6
Abstract 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 parameterizations 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 an equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ₁-norm of the Graver basis is bounded by a function of the maximum ℓ₁-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such an equivalent matrix exists.
Our results yield parameterized algorithms for integer programming when parameterized by the ℓ₁-norm of the Graver basis of the constraint matrix, when parameterized by the ℓ₁-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix equivalent to the constraint matrix.
The talk is based on the results of joint work with M. Briański, M. Koutecký, D. Kráľ, and F. Schröder. ----------------------------------------------------