Huge Unimodular $n$-Fold Programs
Shmuel Onn, Pauline Sarrabezolles · SIAM Journal on Discrete Mathematics · 2015
Optimization over $l\times m\times n$ integer 3-way tables with given line-sums is NP-hard already for fixed $l=3$, but is polynomial time solvable with both $l,m$ fixed. In the huge version of the problem, the variable dimension $n$ is encoded in binary, with $t$ layer types. It was recently shown that the huge problem can be solved in polynomial time for fixed $t$, and the complexity of the problem for variable $t$ was raised as an open problem. Here we solve this problem and show that the huge table problem can be solved in polynomial time even when the number $t$ of types is variable. The complexity of the problem over 4-way tables with variable $t$ remains open, where all we know is that the associated decision problem is in NP intersect coNP. Our treatment goes through the more general class of huge $n$-fold integer programming problems. We show that huge integer programs over $n$-fold products of totally unimodular matrices can be solved in polynomial time even when the number $t$ of brick types is variable.