Tight lower bounds for block-structured integer programs

DOI10.1007/978-3-031-59835-7_17MaRDI QIDQ7030558zbMATH OpenFDO

Authors Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59835-7_17

zbMATH Keywords

(unconditional) lower bounds\(n\)-foldETHinteger programmingmulti-stagesubset sumtree-fold

Mathematics Subject Classification ID

Integer programming (90C10)

Cites work

• \(N\)-fold integer programming
• \(N\)-fold integer programming and nonlinear multi-transshipment
• \(n\)-fold integer programming in cubic time
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• A Priori Optimization of the Probabilistic Traveling Salesman Problem
• About the complexity of two-stage stochastic IPs
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• Combinatorial \(n\)-fold integer programming and applications
• Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity
• Empowering the configuration-IP -- new PTAS results for scheduling with setups times
• Exact solutions to a class of stochastic generalized assignment problems
• Faster Algorithms for Integer Programs with Block Structure
• Finiteness theorems in stochastic integer programming
• scientific article; zbMATH DE number 663895 (Why is no real title available?)
• scientific article; zbMATH DE number 7788439 (Why is no real title available?)
• Integer programming in parameterized complexity: five miniatures
• Near-linear time algorithm for n-fold ILPs via color coding
• Parameterized algorithms for block-structured integer programs with large entries
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• Parameterized complexity of configuration integer programs
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Scheduling kernels via configuration LP
• Scheduling meets n-fold integer programming
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Tight complexity lower bounds for integer linear programming with few constraints
• Tight lower bounds for block-structured integer programs

Cited in

(2)

• (Near)-optimal algorithms for sparse separable convex integer programs
• Tight lower bounds for block-structured integer programs

This page was built for publication: Tight lower bounds for block-structured integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030558)