Parameterized algorithms for block-structured integer programs with large entries
Authors:
- Jana CslovjecsekJCJana Cslovjecsek
- Martin KouteckýMKMartin Koutecký
- Alexandra LassotaALAlexandra Lassota
- Michał PilipczukMPMichał Pilipczuk
- Adam PolakAPAdam Polak
Open Access
- 18 July 2025
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Abstract
We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are bounded-size matrices. On the other hand, $n$-fold programs are integer programs of the form $\{{\sum_{i=1}^n C_i\mathbf{y}_i=\mathbf{a}} \textrm{ and } D_i\mathbf{y}_i=\mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where again $C_i$ and $D_i$ are bounded-size matrices. It is known that solving these kind of programs is fixed-parameter tractable when parameterized by the maximum dimension among the relevant matrices $A_i,C_i,D_i$ and the maximum absolute value of any entry appearing in the constraint matrix. We show that the parameterized tractability results for two-stage stochastic and $n$-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove that: - The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices $A_i,D_i$ and by the maximum absolute value of the entries of matrices $D_i$. That is, we allow matrices $A_i$ to have arbitrarily large entries. - The linear optimization problem for $n$-fold integer programs that are uniform -- all matrices $C_i$ are equal -- is fixed-parameter tractable when parameterized by the dimensions of matrices $C_i$ and $D_i$ and by the maximum absolute value of the entries of matrices $D_i$. That is, we require that $C_i=C$ for all $i=1,\ldots,n$, but we allow $C$ to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is $\mathsf{NP}$-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input.49 pages. This is the TheoretiCS journal version
Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- High-multiplicity N-fold IP via configuration LPMathematical Programming, 2022
- The double exponential runtime is tight for 2-stage stochastic ILPsMathematical Programming, 2022
- About the complexity of two-stage stochastic IPsMathematical Programming, 2021
- Empowering the configuration-IP: new PTAS results for scheduling with setup timesMathematical Programming, 2021
- Combinatorial n-fold integer programming and applicationsMathematical Programming, 2019
- Graver basis and proximity techniques for block-structured separable convex integer minimization problemsMathematical Programming, 2013
- n-Fold integer programming in cubic timeMathematical Programming, 2011
- Minimal solutions of linear diophantine systems : bounds and algorithmsLecture Notes in Computer Science, 1991
- An application of simultaneous diophantine approximation in combinatorial optimizationCombinatorica, 1987
- Elementare Theorie der konvexen PolyederCommentarii Mathematici Helvetici, 1934