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

DOI10.1137/20M1353502zbMath1493.90110arXiv1907.06688OpenAlexW3040869546WikidataQ114074177 ScholiaQ114074177MaRDI QIDQ5864669

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

Publication date: 8 June 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.06688

zbMATH Keywords

integer programmingmatroidsfixed-parameter tractabilitytree-depthbranch-depth

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Uses Software

• GCG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First order convergence of matroids
• Partitioning mathematical programs for parallel solution
• On the excluded minors for the matroids of branch-width \(k\)
• The complexity landscape of decompositional parameters for ILP
• \(n\)-fold integer programming in cubic time
• Branch-depth: generalizing tree-depth of graphs
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• Finiteness theorems in stochastic integer programming
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Integer Programming with a Fixed Number of Variables
• Deciding First Order Properties of Matroids
• Reformulation and Decomposition of Integer Programs
• Minkowski's Convex Body Theorem and Integer Programming
• Decomposing Matrices into Blocks
• Permuting Sparse Rectangular Matrices into Block-Diagonal Form
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Computational Experience with Hypergraph-Based Methods for Automatic Decomposition in Discrete Optimization
• Faster Algorithms for Integer Programs with Block Structure
• Finding branch-decompositions of matroids, hypergraphs, and more
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
• Structure Detection in Mixed-Integer Programs
• On Integer Programming and the Branch-Width of the Constraint Matrix
• Mathematical Foundations of Computer Science 2003
• Parameterized Algorithms
• Systems of distinct representatives and linear algebra
• Rearranging Matrices to Block-Angular form for Decomposition (And Other) Algorithms
• Finding Branch-Decompositions and Rank-Decompositions
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming