Faster Algorithms for Integer Programs with Block Structure

DOI10.4230/LIPIcs.ICALP.2018.49zbMath1503.90075arXiv1802.06289OpenAlexW2963126600MaRDI QIDQ5002724

Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein

Publication date: 28 July 2021

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

zbMATH Keywords

integer programming\(n\)-foldtree-fold

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Integer programming (90C10)

Related Items (19)

About the Complexity of Two-Stage Stochastic IPs ⋮ Integer programming in parameterized complexity: five miniatures ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ A colorful Steinitz lemma with application to block-structured integer programs ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ Unnamed Item ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The clever shopper problem ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times ⋮ Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming ⋮ About the complexity of two-stage stochastic IPs

Cites Work

• \(N\)-fold integer programming
• Nonlinear discrete optimization. An algorithmic theory
• An integer analogue of Carathéodory's theorem
• Value of the Steinitz constant
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• On the complexity of integer programming
• On the foundations of linear and integer linear programming I
• A strongly polynomial algorithm for bimodular integer linear programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Faster Algorithms for Integer Programs with Block Structure