Block-structured integer programming: Can we parameterize without the largest coefficient?

作     者：Chen, Hua Chen, Lin Zhang, Guochuan 

作者机构：Zhejiang Univ Zheda Rd 38 Hangzhou 310027 Zhejiang Peoples R China Texas Tech Univ 2500 Broadway Lubbock TX 79409 USA 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2022年第46卷

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：NSF CCF, United States NSFC, China 2004096 12131003 

主　　题：Integer programming 4-block n-fold IP Fixed parameter tractable 

摘      要：We consider 4-block n-fold integer programming, which can be written as max{w.x : Hx = b, l = x = u, x is an element of Z(N)}, where the constraint matrix H is composed of small matrices A, B, C, D such that the first row of H is (C, D, D, ..., D), the first column of H is (C, B, B, ..., B), the main diagonal of H is (C, A, A, ..., A), and all the other entries are 0. There are n copies of D, B, and A. The special case where B = C = 0 is known as n-fold integer programming. Prior algorithmic results for 4-block n-fold integer programming and its special cases usually take Delta, the largest absolute value among entries of H, as part of the parameters. In this paper, we explore the possibility of solving the problems polynomially when the number of rows and columns of the small matrices are constant. We show that, assuming P not equal NP, this is not possible even if A = (1, 1, Delta) and B = C = 0. However, this becomes possible if A = (1, ..., 1) or A is an element of Z(1x2), or more generally if A is an element of Z(sAxtA), t(A) = s(A) + 1 and the rank of matrix A satisfies that rank(A) = s(A). (C) 2022 Elsevier B.V. All rights reserved.