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

D 2022

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

BRIAŃSKI, Marcin, Martin KOUTECKÝ, Daniel KRÁĽ, Kristýna PEKÁRKOVÁ, Felix SCHRÖDER et. al.

Basic information

Original name

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

Authors

BRIAŃSKI, Marcin (616 Poland), Martin KOUTECKÝ (203 Czech Republic), Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution), Kristýna PEKÁRKOVÁ (203 Czech Republic, belonging to the institution) and Felix SCHRÖDER (276 Germany)

Edition

Dagstuhl, Germany, Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), p. "29:1"-"29:20", 20 pp. 2022

Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/22:00126328

Organization unit

Faculty of Informatics

ISBN

978-3-95977-235-8

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.ICALP.2022.29

Keywords in English

integer programming; width parameters; matroids; Graver basis; tree-depth; fixed parameter tractability

Abstract

V originále

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.

Links

MUNI/A/1145/2021, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Acronym: SV-FI MAV XI.)

Investor: Masaryk University

MUNI/A/1230/2021, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 22 (Acronym: SKOMU)

Investor: Masaryk University

MUNI/I/1677/2018, interní kód MU

Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities

Citovat

BRIAŃSKI, 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 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.

@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.

Detailed Information on Publication Record