Block-structured integer programming: can we parameterize without the largest coefficient?

DOI10.1016/j.disopt.2022.100743OpenAlexW4304701300MaRDI QIDQ2684049

Yanyan Li

Publication date: 16 February 2023

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingfixed parameter tractable4-block \(n\)-fold IP

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• \(N\)-fold integer programming
• Decomposition of test sets in stochastic integer programming
• \(n\)-fold integer programming in cubic time
• Combinatorial \(n\)-fold integer programming and applications
• Scheduling meets \(n\)-fold integer programming
• Finiteness theorems in stochastic integer programming
• Integer Programming with a Fixed Number of Variables
• A Polynomial-Time Algorithm for Optimizing over N-Fold 4-Block Decomposable Integer Programs
• Minkowski's Convex Body Theorem and Integer Programming
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• On the complexity of integer programming
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Reducibility among Combinatorial Problems
• Faster Algorithms for Integer Programs with Block Structure
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• About the Complexity of Two-Stage Stochastic IPs
• Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
• Opinion diffusion and campaigning on society graphs
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Integer Programming and Combinatorial Optimization
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

This page was built for publication: Block-structured integer programming: can we parameterize without the largest coefficient?