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

• 成果类型: Article
• 署名作者: Chen, Hua; Chen, Lin; Zhang, Guochuan
• 署名单位: Zhejiang University; Texas Tech University System; Texas Tech University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02046-z
• 发表日期: 2024
• 页码: 463-496
• 关键词: time algorithm; makespan; bicriteria

摘要

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 lambda <= g(gamma ) such that for any nonzero kernel element g, lambda g can always be decomposed into kernel elements in the same orthant whose l(infinity)-norm is bounded by g(gamma) (while g itself might not admit such a decomposition), where g is a computable function and gamma is an upper bound on the dimensions of the blocks and the largest coefficient. Based on this, we are able to bound the l(infinity)-norm of Graver basis elements by O(g(gamma)n) and develop an O(g(gamma)n(3+o(1))(L) over cap (2))-time algorithm (here (L) over cap denotes the logarithm of the largest absolute value occurring in the input). Additionally, we show that the l(infinity)-norm of Graver basis elements is Omega(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.