D 2020

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

Dagstuhl, Germany, Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), p. "26:1"-"26:19", 19 pp. 2020. p. "26:1"-"26:19", 19 pp. 2020

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/20:00116613

Organization unit

Faculty of Informatics

ISBN

978-3-95977-138-2

ISSN

DOI

Keywords in English

matroid algorithms; width parameters; integer programming; fixed parameter tractability; branch-width; branch-depth

Tags

Tags

International impact, Reviewed
Změněno: 26/4/2021 07:20, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

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.

Links

MUNI/A/1050/2019, interní kód MU
Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Acronym: SV-FI MAV IX)
Investor: Masaryk University, Category A
MUNI/A/1076/2019, interní kód MU
Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Acronym: SKOMU)
Investor: Masaryk University, Category A
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