2018/05/09 by Lin Chen, Lei Xu, Chen, Lin +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1805.03741
arxiv created 2019/10/25 · arxiv updated 2019/10/28
We consider 4-block n-fold integer programs, whose constraint matrix consists of n copies of small matrices A, B, and D, and one copy of C, in a specific block structure. All existing algorithms along this line of research follows an iterative augmentation framework, which relies on the so-called Graver basis of the constraint matrix that constitutes a set of fundamental augmenting steps. Bounding the ℓ1- or ℓ_∞-norm of elements of the Graver basis is the key to these algorithms. Hemmecke et al.~[Math. Prog. 2014] showed that 4-block n-fold IP has Graver elements of ℓ_∞-norm at most OFPT(n^2^sD), leading to an algorithm with a similar runtime; here, sD is the number of rows of matrix D and OFPT(1) hides a multiplicative factor that is only dependent on the small matrices A,B,C,D. We prove that the ℓ∞-norm of the Graver elements of 4-block n-fold IP is upper bounded by OFPT(n^sD), improving significantly over the previous bound OFPT (n^2^sD). We also provide a matching lower bound of Ω(n^sD) which even holds for arbitrary non-zero lattice elements, ruling out augmenting algorithm relying on even more restricted notions of augmentation than the Graver basis. 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 while even there the ℓ∞-norm of its Graver elements is Ω(n^sD), there exists a different decomposition into lattice elements whose ℓ∞-norm is bounded by OFPT(1), which allows us to provide improved upper bounds on the ℓ∞-norm of Graver elements for 3-block n-fold IP.