2026-07-25T06:06:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25147 2026-02-11T15:00:34Z ddc:004 open_access

New Algorithm for Combinatorial n-Folds and Applications Jansen, Klaus Kahler, Kai Pirotton, Lis Tutas, Malte integer linear programming n-fold parameterized complexity scheduling uniform machines Block-structured integer linear programs (ILPs) play an important role in various application fields. We address n-fold ILPs where the matrix 𝒜 has a specific structure, i.e., where the blocks in the lower part of 𝒜 consist only of the row vectors (1,… ,1). In this paper, we propose an approach tailored to exactly these combinatorial n-folds. We utilize a divide and conquer approach to separate the original problem such that the right-hand side iteratively decreases in size. We show that this decrease in size can be calculated such that we only need to consider a bounded amount of possible right-hand sides. This, in turn, lets us efficiently combine solutions of the smaller right-hand sides to solve the original problem. We can decide the feasibility of, and also optimally solve, such problems in time (n r Δ)^O(r) log(‖b‖_∞), where n is the number of blocks, r the number of rows in the upper blocks and Δ = ‖A‖_∞. We complement the algorithm by discussing applications of the n-fold ILPs with the specific structure we require. We consider the problems of (i) scheduling on uniform machines, (ii) closest string and (iii) (graph) imbalance. Regarding (i), our algorithm results in running times of p_max^O(d)|I|^O(1), matching a lower bound derived via ETH. For (ii) we achieve running times matching the current state-of-the-art in the general case. In contrast to the state-of-the-art, our result can leverage a bounded number of column-types to yield an improved running time. For (iii), we improve the parameter dependency on the size of the vertex cover. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus Jansen and Kai Kahler and Lis Pirotton and Malte Tutas 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.15 urn:nbn:de:0030-drops-251472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode