Matrices of Optimal Tree-Depth and a Row-Invariant
Parameterized Algorithm for Integer Programming

J 2022

Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming

CHAN, Timothy Fong Nam; Jacob COOPER; Martin KOUTECKÝ; Daniel KRÁĽ; Kristýna PEKÁRKOVÁ et. al.

Basic information

Original name

Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming

Authors

CHAN, Timothy Fong Nam (826 United Kingdom of Great Britain and Northern Ireland); Jacob COOPER (826 United Kingdom of Great Britain and Northern Ireland, belonging to the institution); Martin KOUTECKÝ (203 Czech Republic); Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution) and Kristýna PEKÁRKOVÁ (203 Czech Republic, belonging to the institution)

Edition

SIAM JOURNAL ON COMPUTING, UNITED STATES, SIAM PUBLICATIONS, 2022, 0097-5397

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

is not subject to a state or trade secret

References:

URL

Impact factor

Impact factor: 1.600

RIV identification code

RIV/00216224:14330/22:00126436

Organization unit

Faculty of Informatics

DOI

https://doi.org/10.1137/20M1353502

UT WoS

001130401900013

EID Scopus

2-s2.0-85132215614

Keywords in English

branch-depth; fixed-parameter tractability; integer programming; matroids; tree-depth

Abstract

In the original language

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry Δ are solvable in time g(d, Δ)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual treedepth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d∗, Δ)poly(n) where d∗ is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.

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/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

CHAN, Timothy Fong Nam; Jacob COOPER; Martin KOUTECKÝ; Daniel KRÁĽ and Kristýna PEKÁRKOVÁ. Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming. SIAM JOURNAL ON COMPUTING. UNITED STATES: SIAM PUBLICATIONS, 2022, vol. 51, No 3, p. 664-700. ISSN 0097-5397. Available from: https://doi.org/10.1137/20M1353502.

@article{2211686,
   author = {Chan, Timothy Fong Nam and Cooper, Jacob and Koutecký, Martin and Kráľ, Daniel and Pekárková, Kristýna},
   article_location = {UNITED STATES},
   article_number = {3},
   doi = {https://doi.org/10.1137/20M1353502},
   keywords = {branch-depth; fixed-parameter tractability; integer programming; matroids; tree-depth},
   language = {eng},
   issn = {0097-5397},
   journal = {SIAM JOURNAL ON COMPUTING},
   title = {Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming},
   url = {https://epubs.siam.org/doi/10.1137/20M1353502},
   volume = {51},
   year = {2022}
}

TY  - JOUR
ID  - 2211686
AU  - Chan, Timothy Fong Nam - Cooper, Jacob - Koutecký, Martin - Kráľ, Daniel - Pekárková, Kristýna
PY  - 2022
TI  - Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming
JF  - SIAM JOURNAL ON COMPUTING
VL  - 51
IS  - 3
SP  - 664-700
EP  - 664-700
PB  - SIAM PUBLICATIONS
SN  - 00975397
KW  - branch-depth
KW  - fixed-parameter tractability
KW  - integer programming
KW  - matroids
KW  - tree-depth
UR  - https://epubs.siam.org/doi/10.1137/20M1353502
N2  - A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry Δ are solvable in time g(d, Δ)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual treedepth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d∗, Δ)poly(n) where d∗ is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.
ER  -

CHAN, Timothy Fong Nam; Jacob COOPER; Martin KOUTECKÝ; Daniel KRÁĽ and Kristýna PEKÁRKOVÁ. Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming. \textit{SIAM JOURNAL ON COMPUTING}. UNITED STATES: SIAM PUBLICATIONS, 2022, vol.~51, No~3, p.~664-700. ISSN~0097-5397. Available from: https://doi.org/10.1137/20M1353502.

Přehled o publikaci