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

作     者：Brianski, Marcin Koutecky, Martin Kral, Daniel Pekarkova, Kristyna Schroder, Felix 

作者机构：Jagiellonian Univ Fac Math & Comp Sci Theoret Comp Sci Dept Krakow Poland Charles Univ Prague Comp Sci Inst Prague Czech Republic Masaryk Univ Fac Informat Brno Czech Republic Charles Univ Prague Fac Math & Phys Prague Czech Republic 

出 版 物：《MATHEMATICAL PROGRAMMING》 (Math. Program.)

年 卷 期：2024年第208卷第1-2期

页      面：497-531页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 

基　　金：Masarykova Univerzita 

主　　题：Integer programming Width parameters Matroids Graver basis Tree-depth Fixed parameter tractability 

摘      要：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 l(1)-norm of the Graver basis is bounded by a function of the maximum l(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 such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the l(1)-norm of the Graver basis of the constraint matrix, when parameterized by the l(1)-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.