English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An intensive line of research on fixed parameter tractability of integerprogramming is focused on exploiting the relation between the sparsity of aconstraint matrix $A$ and the norm of the elements of its Graver basis. Inparticular, integer programming is fixed parameter tractable when parameterizedby the primal tree-depth and the entry complexity of $A$, and whenparameterized by the dual tree-depth and the entry complexity of $A$; boththese parameterization imply that $A$ is sparse, in particular, the number ofits non-zero entries is linear in the number of columns or rows, respectively.  We study preconditioners transforming a given matrix to a row-equivalentsparse matrix if it exists and provide structural results characterizing theexistence of a sparse row-equivalent matrix in terms of the structuralproperties of the associated column matroid. In particular, our results implythat the $\ell_1$-norm of the Graver basis is bounded by a function of themaximum $\ell_1$-norm of a circuit of $A$. We use our results to design aparameterized algorithm that constructs a matrix row-equivalent to an inputmatrix $A$ that has small primal/dual tree-depth and entry complexity if such arow-equivalent matrix exists.  Our results yield parameterized algorithms for integer programming whenparameterized by the $\ell_1$-norm of the Graver basis of the constraintmatrix, when parameterized by the $\ell_1$-norm of the circuits of theconstraint matrix, when parameterized by the smallest primal tree-depth andentry complexity of a matrix row-equivalent to the constraint matrix, and whenparameterized by the smallest dual tree-depth and entry complexity of a matrixrow-equivalent to the constraint matrix.

Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming