Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1684015,
author = {Chan, Timothy Fong Nam and Cooper, Jacob and Koutecký, Martin and Kráľ, Daniel and Pekárková, Kristýna},
address = {Dagstuhl, Germany},
booktitle = {Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), p. "26:1"-"26:19", 19 pp. 2020.},
doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2020.26},
keywords = {matroid algorithms; width parameters; integer programming; fixed parameter tractability; branch-width; branch-depth},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl, Germany},
isbn = {978-3-95977-138-2},
pages = {"26:1"-"26:19"},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
title = {Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming},
year = {2020}
}
TY - JOUR
ID - 1684015
AU - Chan, Timothy Fong Nam - Cooper, Jacob - Koutecký, Martin - Kráľ, Daniel - Pekárková, Kristýna
PY - 2020
TI - Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY - Dagstuhl, Germany
SN - 9783959771382
KW - matroid algorithms
KW - width parameters
KW - integer programming
KW - fixed parameter tractability
KW - branch-width
KW - branch-depth
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 D are solvable in time g(d,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 tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,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. In \textit{Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), p. ''26:1''-''26:19'', 19 pp. 2020.}. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. p.~''26:1''-''26:19'', 19 pp. ISBN~978-3-95977-138-2. doi:10.4230/LIPIcs.ICALP.2020.26. 2020.
|
