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.

Základní údaje

Originální název

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

Autoři

BRIAŃSKI, Marcin (616 Polsko), Martin KOUTECKÝ (203 Česká republika), Daniel KRÁĽ (203 Česká republika, garant, domácí), Kristýna PEKÁRKOVÁ (203 Česká republika, domácí) a Felix SCHRÖDER (276 Německo)

Vydání

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

Nakladatel

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/22:00126328

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-235-8

ISSN

DOI

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

Klíčová slova anglicky

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

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 13. 1. 2023 09:41, prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Anotace

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.

Návaznosti

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

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

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.

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

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

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 22

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

Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)

Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities

Citovat

BRIAŃSKI, Marcin, Martin KOUTECKÝ, Daniel KRÁĽ, Kristýna PEKÁRKOVÁ a 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, s. "29:1"-"29:20", 20 s. ISBN 978-3-95977-235-8. Dostupné z: 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Á a 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, s.~''29:1''-''29:20'', 20 s. ISBN~978-3-95977-235-8. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ICALP.2022.29.

Podrobný výpis o publikaci