Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1876400,
author = {Briański, Marcin and Koutecký, Martin and Kráľ, Daniel and Pekárková, Kristýna and Schröder, Felix},
address = {Dagstuhl, Germany},
booktitle = {Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2022.29},
keywords = {integer programming; width parameters; matroids; Graver basis; tree-depth; fixed parameter tractability},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl, Germany},
isbn = {978-3-95977-235-8},
pages = {"29:1"-"29:20"},
publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
title = {Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming},
year = {2022}
}
TY - JOUR
ID - 1876400
AU - Briański, Marcin - Koutecký, Martin - Kráľ, Daniel - Pekárková, Kristýna - Schröder, Felix
PY - 2022
TI - Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming
PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik
CY - Dagstuhl, Germany
SN - 9783959772358
KW - integer programming
KW - width parameters
KW - matroids
KW - Graver basis
KW - tree-depth
KW - fixed parameter tractability
N2 - 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.
ER -
BRIA$\backslash$'NSKI, Marcin, Martin KOUTECKÝ, Daniel KRÁĽ, Kristýna PEKÁRKOVÁ and Felix SCHRÖDER. Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming. Online. In \textit{Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, p.~''29:1''-''29:20'', 20 pp. ISBN~978-3-95977-235-8. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2022.29.
|
