On the Graver basis of block-structured integer programming
share
We consider the 4-block n-fold integer programming (IP), in which the constraint matrix consists of n copies of small matrices A, B, D and one copy of C in a specific block structure. We prove that, the ℓ_∞-norm of the Graver basis elements of 4-block n-fold IP is upper bounded by O_FPT(n^s_c) where s_c is the number of rows of matrix C and O_FPT hides a multiplicative factor that is only dependent on the parameters of the small matrices A,B,C,D (i.e., the number of rows and columns, and the largest absolute value among the entries). This improves upon the existing upper bound of O_FPT(n^2^s_c). We provide a matching lower bounded of Ω(n^s_c), which even holds for an arbitrary non-zero integral element in the kernel space. We then consider a special case of 4-block n-fold in which C is a zero matrix (called 3-block n-fold IP). We show that, surprisingly, 3-block n-fold IP admits a Hilbert basis whose ℓ_∞-norm is bounded by O_FPT(1), despite the fact that the ℓ_∞-norm of its Graver basis elements is still Ω(n). Finally, we provide upper bounds on the ℓ_∞-norm of Graver basis elements for 3-block n-fold IP. Based on these upper bounds, we establish algorithms for 3-block n-fold IP and provide improved algorithms for 4-block n-fold IP.
READ FULL TEXT