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

J 2024

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, belonging to the institution); Kristýna PEKÁRKOVÁ (203 Czech Republic, belonging to the institution) and Felix SCHRÖDER (276 Germany)

Edition

MATHEMATICAL PROGRAMMING, Berlin, Germany, SPRINGER HEIDELBERG, 2024, 0025-5610

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

is not subject to a state or trade secret

References:

URL

Impact factor

Impact factor: 2.500

RIV identification code

RIV/00216224:14330/24:00137365

Organization unit

Faculty of Informatics

DOI

https://doi.org/10.1007/s10107-023-02048-x

UT WoS

001145544400002

EID Scopus

2-s2.0-85182671269

Keywords in English

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

Abstract

In the original language

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.

Links

MUNI/A/1592/2023, interní kód MU

Name: Modelování, analýza a verifikace (2024)

Investor: Masaryk University, Modeling, analysis, and verification (2024)

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

Cite

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. MATHEMATICAL PROGRAMMING. Berlin, Germany: SPRINGER HEIDELBERG, 2024, vol. 208, 1-2, p. 497-531. ISSN 0025-5610. Available from: https://doi.org/10.1007/s10107-023-02048-x.

@article{2444621,
   author = {Briański, Marcin and Koutecký, Martin and Kráľ, Daniel and Pekárková, Kristýna and Schröder, Felix},
   article_location = {Berlin, Germany},
   article_number = {1-2},
   doi = {https://doi.org/10.1007/s10107-023-02048-x},
   keywords = {Integer programming; width parameters; matroids; Graver basis; tree-depth; fixed-parameter tractability},
   language = {eng},
   issn = {0025-5610},
   journal = {MATHEMATICAL PROGRAMMING},
   title = {Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming},
   url = {https://link.springer.com/article/10.1007/s10107-023-02048-x},
   volume = {208},
   year = {2024}
}

TY  - JOUR
ID  - 2444621
AU  - Briański, Marcin - Koutecký, Martin - Kráľ, Daniel - Pekárková, Kristýna - Schröder, Felix
PY  - 2024
TI  - Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming
JF  - MATHEMATICAL PROGRAMMING
VL  - 208
IS  - 1-2
SP  - 497-531
EP  - 497-531
PB  - SPRINGER HEIDELBERG
SN  - 00255610
KW  - Integer programming
KW  - width parameters
KW  - matroids
KW  - Graver basis
KW  - tree-depth
KW  - fixed-parameter tractability
UR  - https://link.springer.com/article/10.1007/s10107-023-02048-x
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 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.
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. \textit{MATHEMATICAL PROGRAMMING}. Berlin, Germany: SPRINGER HEIDELBERG, 2024, vol.~208, 1-2, p.~497-531. ISSN~0025-5610. Available from: https://doi.org/10.1007/s10107-023-02048-x.

Přehled o publikaci