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.

Základní údaje

Originální název

Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming

Autoři

CHAN, Timothy Fong Nam (826 Velká Británie a Severní Irsko), Jacob COOPER (826 Velká Británie a Severní Irsko, domácí), Martin KOUTECKÝ (203 Česká republika), Daniel KRÁĽ (203 Česká republika, garant, domácí) a Kristýna PEKÁRKOVÁ (203 Česká republika, domácí)

Vydání

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

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/20:00116613

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-138-2

ISSN

DOI

Klíčová slova anglicky

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

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 26. 4. 2021 07:20, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

MUNI/A/1050/2019, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Akronym: SV-FI MAV IX)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1076/2019, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/I/1677/2018, interní kód MU
Název: MUNI AWARD in Science and Humanitites 1 (Akronym: MASH 1)
Investor: Masarykova univerzita, MUNI AWARD in Science and Humanitites 1, MASH - MUNI Award in Science and Humanities