A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity

DOI10.1007/978-3-662-48350-3_65zbMath1466.68046arXiv1506.07729OpenAlexW789853836MaRDI QIDQ3452840

Bart M. P. Jansen, Stefan Kratsch

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Integer programming (90C10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (9)

Parameterized Resiliency Problems via Integer Linear Programming ⋮ A Retrospective on (Meta) Kernelization ⋮ A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ The complexity landscape of decompositional parameters for ILP ⋮ Unnamed Item ⋮ Parameterized resiliency problems

Uses Software

• CPLEX

Cites Work

• Integer-programming software systems
• A partial k-arboretum of graphs with bounded treewidth
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• Kernelization – Preprocessing with a Guarantee
• On Polynomial Kernels for Sparse Integer Linear Programs.
• Incompressibility through Colors and IDs
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity