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

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

CHAN Timothy Fong Nam COOPER Jacob KOUTECKÝ Martin KRÁĽ Daniel PEKÁRKOVÁ Kristýna

Rok publikování 2022
Druh Článek v odborném periodiku
Časopis / Zdroj SIAM JOURNAL ON COMPUTING
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://epubs.siam.org/doi/10.1137/20M1353502
Doi http://dx.doi.org/10.1137/20M1353502
Klíčová slova branch-depth; fixed-parameter tractability; integer programming; matroids; tree-depth
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.