FPT algorithms for a special block-structured integer program with applications in scheduling.

In this paper, a special case of the generalized 4-block n-fold IPs is investigated, where B i = B and B has a rank at most 1. Such IPs, called almost combinatorial 4-block n-fold IPs, include the generalized n-fold IPs as a subcase. We are interested in fixed parameter tractable (FPT) algorithms by taking as parameters the dimensions of the blocks and the largest coefficient. For almost combinatorial 4-block n-fold IPs, we first show that there exists some λ ≤ g (γ) such that for any nonzero kernel element g , λ g can always be decomposed into kernel elements in the same orthant whose ℓ ∞ -norm is bounded by g (γ) (while g itself might not admit such a decomposition), where g is a computable function and γ is an upper bound on the dimensions of the blocks and the largest coefficient. Based on this, we are able to bound the ℓ ∞ -norm of Graver basis elements by O (g (γ) n) and develop an O (g (γ) n 3 + o (1) L ^ 2) -time algorithm (here L ^ denotes the logarithm of the largest absolute value occurring in the input). Additionally, we show that the ℓ ∞ -norm of Graver basis elements is Ω (n) . As applications, almost combinatorial 4-block n-fold IPs can be used to model generalizations of classical problems, including scheduling with rejection, bi-criteria scheduling, and a generalized delivery problem. Therefore, our FPT algorithm establishes a general framework to settle these problems. [ABSTRACT FROM AUTHOR]