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. Online. 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, 2020, p.~''26:1''-''26:19'', 19 pp. ISBN~978-3-95977-138-2. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2020.26.
|