@online{Cslovjecsek_2311.01890,
TITLE = {Parameterized Algorithms for Block-structured Integer Programs with Large Entries},
AUTHOR = {Cslovjecsek, Jana and Kouteck{\'y}, Martin and Lassota, Alexandra and Pilipczuk, Micha{\l} and Polak, Adam},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2311.01890},
EPRINT = {2311.01890},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We study two classic variants of block-structured integer programming.<br>Two-stage stochastic programs are integer programs of the form $\{A_i<br>\mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$,<br>where $A_i$ and $D_i$ are bounded-size matrices. On the other hand, $n$-fold<br>programs are integer programs of the form $\{{\sum_{i=1}^n<br>C_i\mathbf{y}_i=\mathbf{a}} \textrm{ and } D_i\mathbf{y}_i=\mathbf{b}_i\textrm{<br>for all }i=1,\ldots,n\}$, where again $C_i$ and $D_i$ are bounded-size<br>matrices. It is known that solving these kind of programs is fixed-parameter<br>tractable when parameterized by the maximum dimension among the relevant<br>matrices $A_i,C_i,D_i$ and the maximum absolute value of any entry appearing in<br>the constraint matrix.<br> We show that the parameterized tractability results for two-stage stochastic<br>and $n$-fold programs persist even when one allows large entries in the global<br>part of the program. More precisely, we prove that:<br> -- The feasibility problem for two-stage stochastic programs is<br>fixed-parameter tractable when parameterized by the dimensions of matrices<br>$A_i,D_i$ and by the maximum absolute value of the entries of matrices $D_i$.<br>That is, we allow matrices $A_i$ to have arbitrarily large entries.<br> -- The linear optimization problem for $n$-fold integer programs that are<br>uniform -- all matrices $C_i$ are equal -- is fixed-parameter tractable when<br>parameterized by the dimensions of matrices $C_i$ and $D_i$ and by the maximum<br>absolute value of the entries of matrices $D_i$. That is, we require that<br>$C_i=C$ for all $i=1,\ldots,n$, but we allow $C$ to have arbitrarily large<br>entries.<br> In the second result, the uniformity assumption is necessary; otherwise the<br>problem is $\mathsf{NP}$-hard already when the parameters take constant values.<br>Both our algorithms are weakly polynomial: the running time is measured in the<br>total bitsize of the input.<br>},
}