On 3 April 2023 09:50:19 CEST, Mykhaylo Tyomkyn <tyomkyn@kam.mff.cuni.cz> wrote:

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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz
To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz