1 Search Results for "Cooper, Jacob W."

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.26
Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming

Authors: Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

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.
Cite as

Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková. Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ICALP.2020.26,
  author =	{Chan, Timothy F. N. and Cooper, Jacob W. and Kouteck\'{y}, Martin and Kr\'{a}l', Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na},
  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 =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.26},
  URN =		{urn:nbn:de:0030-drops-124339},
  doi =		{10.4230/LIPIcs.ICALP.2020.26},
  annote =	{Keywords: Matroid algorithms, width parameters, integer programming, fixed parameter tractability, branch-width, branch-depth}
}
  • Refine by Author
  • 1 Chan, Timothy F. N.
  • 1 Cooper, Jacob W.
  • 1 Koutecký, Martin
  • 1 Král', Daniel
  • 1 Pekárková, Kristýna

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Matroids and greedoids

  • Refine by Keyword
  • 1 Matroid algorithms
  • 1 branch-depth
  • 1 branch-width
  • 1 fixed parameter tractability
  • 1 integer programming
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact