Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Medientyp: E-Artikel; Elektronischer Konferenzbericht; Sonstige Veröffentlichung

Titel: Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Beteiligte: Briański, Marcin [VerfasserIn]; Koutecký, Martin [VerfasserIn]; Král', Daniel [VerfasserIn]; Pekárková, Kristýna [VerfasserIn]; Schröder, Felix [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ICALP.2022.29

Schlagwörter: matroids ; Graver basis ; Integer programming ; fixed parameter tractability ; width parameters ; tree-depth

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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 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.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: