Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455461" target="_blank" >RIV/00216208:11320/22:10455461 - isvavai.cz</a>

Alternative codes found

RIV/00216224:14330/22:00126328

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.ICALP.2022.29" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2022.29</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2022.29" target="_blank" >10.4230/LIPIcs.ICALP.2022.29</a>

Result language

angličtina

Original language name

Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Original language description

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to an equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ1-norm of the Graver basis is bounded by a function of the maximum ℓ1-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such an equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the ℓ1-norm of the Graver basis of the constraint matrix, when parameterized by the ℓ1-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix equivalent to the constraint matrix.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-235-8

ISSN

—

e-ISSN

—

Number of pages

20

Pages from-to

1-20

Publisher name

Schloss Dagstuhl

Place of publication

Dagstuhl

Event location

Paříž

Event date

Jul 4, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—