 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-124339
URL:

; ; ; ;

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

 pdf-format:

### Abstract

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 tree-depth d and largest entry Δ are solvable in time g(d,Δ) poly(n) for some function g, i.e., fixed parameter tractable when parameterized by tree-depth d and Δ. However, the tree-depth of a constraint matrix depends on the positions of its non-zero entries and thus does not reflect its geometric structure. In particular, 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. We prove that the branch-depth of the matroid defined by the columns of the constraint matrix is equal to the minimum tree-depth of a row-equivalent matrix. We also design a fixed parameter algorithm parameterized by an integer d and the entry complexity of an input matrix that either outputs a matrix with the smallest dual tree-depth that is row-equivalent to the input matrix or outputs that there is no matrix with dual tree-depth at most d that is row-equivalent to the input matrix. Finally, we use these results to obtain a fixed parameter algorithm for integer programming parameterized by the branch-depth of the input constraint matrix and the entry complexity. The parameterization by branch-depth cannot be replaced by the more permissive notion of branch-width.

### BibTeX - Entry

```@InProceedings{chan_et_al:LIPIcs:2020:12433,
author =	{Timothy F. N. Chan and Jacob W. Cooper and Martin Kouteck{\'y} and Daniel Kr{\'a}l' and Krist{\'y}na Pek{\'a}rkov{\'a}},
title =	{{Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming}},
booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages =	{26:1--26:19},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-138-2},
ISSN =	{1868-8969},
year =	{2020},
volume =	{168},
editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 