Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling

Abstract

We consider so-called $N$-fold integer programs (IPs) of the form $\max \{c^{T}x:Ax=b,\ell \le x\le u,x\in {\mathbb{Z}}^{nt}\},where$A \in \mathbb Z^{(r+sn)\times nt} consists of $n$ arbitrary matrices $A^{(i)}\in {\mathbb{Z}}^{r\times t}$ on a horizontal, and $n$ arbitrary matrices $B^{(j)}\in {\mathbb{Z}}^{s\times t}onadiagonalline.Severalrecentworksdesignfixed-parameteralgorithmsfor$N$-foldIPsbytakingasparametersthenumbersofrowsandcolumnsofthe$A$-and$B$-matrices,togetherwiththelargestabsolutevalue$Δ$overtheirentries.Theseadvancesprovidefastalgorithmsforseveralwell-studiedcombinatorialoptimizationproblemsonstrings,ongraphs,andinmachinescheduling.Inthiswork,weextendthisresearchbyproposingalgorithmsthatadditionallyharnessapartitionstructureofsubmatrices$A^{(i)}$and$B^{(j)}$,whererowindicesofnon-zeroentriesdonotoverlapbetweenanytwosetsinthepartition.Ourmainresultisanalgorithmforsolvingany$N$-foldIPintime$nt log(nt)L^2(S_A)^{O(r+s)}(p_Ap_BΔ)^{O(rp_Ap_B+sp_Ap_B)}$,where$p_A$and$p_B$arethesizeofthelargestsetinsuchapartitionof$A^{(i)}$and$B^{(j)}$,respectively,$S_A$isthenumberofpartsinthepartitionof$A = (A^{(1)},..., A^{(n)}), and $L=(log(||u-\ell |{|}_{\infty })\cdot (log(ma{x}_{x:\ell \le x\le u}|c^{T}x|))$ is a measure of the input. We show that these new structural parameters are naturally small in high-multiplicity scheduling problems, such as makespan minimization on related and unrelated machines, with and without release times, the Santa Claus objective, and the weighted sum of completion times. In essence, we obtain algorithms that are exponentially faster than previous works by Knop et al. (ESA 2017) and Eisenbrand et al./Kouteck{ý} et al. (ICALP 2018) in terms of the number of job types.

arXiv commentThe main technical result, Lemma 4, has a major error in the proof: The claim in the proof "... we could decompose $y^i$, and therefore $y$ into at least two sign-compatible, non-zero cycles of $\mc A$ ..." is NOT true. This claim is based on our claim in Lemma 3 that the decomposition of cycles $y^i$ into bricks $y^{i^j}$ yields cycles $y^{i^j}$ of the N-fold matrix $\mc A$. This is not true