New Algorithm for Combinatorial n-Folds and Applications

Let $r,s,t,n\in {\mathbb{Z}}_{\ge 0}$. An $n$-fold ILP is an integer linear program with RHS vector $b\in {\mathbb{Z}}^{r+ns}$ and with a constraint matrix of the form

where $A_1,\mathrm{\dots },A_n\in {\mathbb{Z}}^{r\times t}$ and $B_1,\mathrm{\dots },B_n\in {\mathbb{Z}}^{s\times t}$ are matrices, and $x=(x_1,\mathrm{\dots },x_n)$ is the desired solution. In other words, if we delete the first $r$ constraints, which are called the global constraints, the problem decomposes into independent programs, which are called local. If $\mathrm{\Delta }$ is the largest absolute value in $A_i$ and $B_i$, $n$-fold integer programs can be solved in time ${(nt)}^{(1+o(1))}\cdot 2^{O(r{s}^2)}{(rs\mathrm{\Delta })}^{O(r^{2}s+s^2)}$ [8]. This algorithm comes as the latest development in a series of improvements spanning almost twenty years [1, 8, 9, 32, 10, 16, 20, 30]. $n$-fold integer programs have already found applications in countless problems, often yielding improved running times over other techniques. As the total number of applications is too large, we refer the reader to [7, 32, 14, 19, 25, 26, 28] for some examples.

In the following, we focus on combinatorial $n$-fold ILPs where we allow blocks of different width, i.e., $t\in {\mathbb{Z}}_{\ge 0}^n$ is a vector and therefore, the block $i\in [n]$ has $t_i$ columns. Also, we have $B_i={(1,\mathrm{\dots },1)}^T={\mathrm{𝟙}}_{t_i}$ for all $i\in [n]$ which implies $s=1$. Thus, we have the following ILP

with $A_i\in {\mathbb{Z}}^{r\times t_i}$ for all $i\in [n]$, $b\in {\mathbb{Z}}^{r+n}$ and where $h:={\sum }_{i\in [n]}{t}_i$ is the total number of columns in $𝒜$. The currently best known algorithms for such combinatorial $n$-fold ILPs have parameter dependency ${(r\mathrm{\Delta })}^{O(r^2)}$ [8, 28]. In our work, we often consider the upper part of the vector $b$ differently from its lower part. Therefore, we introduce the following notation: $b={(b^{\uparrow },b^{\downarrow })}^T$ with $b^{\uparrow }\in {\mathbb{Z}}^r$ and $b^{\downarrow }\in {\mathbb{Z}}^n$. Also, define $b_{\max }^{\uparrow }:={\max }_{j\in [r]}{b}_j^{\uparrow },$ $b_{\max }^{\downarrow }:={\max }_{k\in [n]}{b}_k^{\downarrow }$ and $b_{\text{def}}:=\min (b_{\max }^{\uparrow },b_{\max }^{\downarrow })$.

In this paper, we provide a novel approach to solving such combinatorial $n$-fold ILPs. While the idea of the algorithm we provide is inspired by Jansen and Rohwedder [21], we note that we utilize the structure of $n$-fold ILPs to generate different techniques to split solutions apart into smaller sub-solutions. Using these techniques, we achieve the following result.

Comparatively, the algorithm in [21] yields a running time of $O{(\sqrt{r+n}\mathrm{\Delta })}^{2(r+n)}+O(h\cdot (r+n))$ when applied to our setting, while the state-of-the-art algorithm [8] achieves a running time of ${(n{\Vert t\Vert }_{\mathrm{\infty }})}^{(1+o(1))}\cdot 2^{O(r)}{(r\mathrm{\Delta })}^{O(r^2)}$.

To complement the general techniques we provide to solve combinatorial $n$-fold ILPs, we show how our result can be applied to common problems. First, we consider scheduling on uniform machines with the objective of makespan minimization $(Q\parallel C_{\max })$ and Santa Claus $(Q\parallel C_{\min })$. After publication of a preliminary version of our results, Rohwedder [37] recently bounded $\mathrm{\Delta }$ by $p_{\max }^{O(1)}$ for $Q\parallel C_{\max }$, where $p_{\max }$ is the largest processing time. They also provide an (almost) tight algorithm for $Q\parallel C_{\max }$ with running time ${(d{p}_{\max })}^{O(d)}{(h+M)}^{O(1)}{|I|}^{O(1)}$, where $d$ is the number of job-types, $h$ is the total number of columns in the configuration ILP and $M$ is the total number of machines. Replacing a subroutine in [37] by our algorithm improves their result to ${(d{p}_{\max })}^{O(d)}\log (m_{\text{def}}){|I|}^{O(1)}$, where $m_{\text{def}}:=\min (n_{\max },m_{\max })$ i.e., we achieve a better result with respect to parameter $h$ and $M$. This answers the open question by Koutecký and Zink in [31]. They pose the question whether $Q\parallel C_{\max }$ can be solved in time $p_{\max }^{O(d)}{|I|}^{O(1)}$. In more detail, the calculation of the Multi-Choice IP in [37] has a running time of ${(nr\mathrm{\Delta })}^{O(r)}(h+{\Vert b^{\downarrow }\Vert }_1)$, while our $n$-fold algorithm runs in ${(nr\mathrm{\Delta })}^{O(r)}\log (b_{\text{def}})$, i.e., solves these Multi-Choice IPs more quickly.

We also manage to extend these techniques to $Q\parallel C_{\min }.$ This yields running times that are (almost) tight by an ETH-lower bound.

We also apply our algorithm to the Closest String problem and the Imbalance problem (see Section 4 for formal definitions). The current best running times [28] for both problems have a quadratic dependency of $k$ in the exponent, where $k$ is the number of considered strings (Closest String), respectively the size of the vertex cover (Imbalance). When the number of column-types (Closest String), respectively vertex-types (Imbalance) is bounded by $T$, our algorithm achieves the following results.

Generally, $T$ is bounded by $k^k$ for Closest String. In this case, we meet the state-of-the-art parameter dependency. For Imbalance, $T$ may take any integer value up to $2^k$. The resulting parameter dependency of $2^{k^2}$ improves on the state-of-the-art $k^{k^2}$ which is the application of [28] to the problem. Additionally, when $T$ is bounded by $k^{O(1)}$, we are able to reduce the dependency in the exponent to linear for both problems. When applying Rohwedder’s algorithm for the Multi-Choice IP [37, Theorem 2] to those problems, the resulting running times are ${((T+1)k)}^{O(k)}O(T+dk)$, where $d$ is the upper bound on string distance (Closest String) and ${((T+2)k)}^{O(k)}O(Tk+nk)$ (Imbalance).

We expect that our techniques can be extended to several other problems that can be formulated as a combinatorial $n$-fold ILP as well, such as the string problems given in [28].

Integer linear programming is one of the twenty-one problems originally proven to be NP-hard by Karp in his seminal work [24]. Since then, ILPs have been used to solve countless NP-hard problems, for examples see e.g. [14]. The currently best known running times can be separated by their parameterization. When considering a small number of constraints $m$, the best known running time is given by Jansen and Rohwedder [21], and runs in time $O{(\sqrt{m}\mathrm{\Delta })}^{(1+o(1))m}+O(nm).$ For a small number of variables $n$, the current best known algorithm is given by Reis and Rothvoss [36], with a running time of ${(\log n)}^{O(n)}\cdot {|𝒜|}^{O(1)}$.

With the general ILP being a hard problem, research into certain substructures that are more easily solvable began. For an overview of this process, see e.g., [11, 14]. Of particular interest to this paper is the $n$-fold ILP, whose current best known algorithm is given by Cslovjecsek, Eisenbrand, Hunkenschröder, Rohwedder and Weismantel [8]. Their algorithm runs in time ${(nt)}^{(1+o(1))}\cdot 2^{O(r{s}^2)}{(rs\mathrm{\Delta })}^{O(r^{2}s+s^2)}$ and is the latest result in a series of improvements that spans close to twenty years, see [9, 32, 10, 16, 20, 30] for works complementing this line of research.

Scheduling is one of the most well-known operations research problems. We now specifically turn towards uniform machines. By formulating the problem as an $n$-fold ILP, Knop and Koutecký [29] showed that $Q\parallel C_{\max }$ can be solved in time $p_{\max }^{O(p_{\max }^2)}{|I|}^{O(1)}$ if the number of machines is encoded in unary. By solving a relaxation to schedule many of the jobs in advance and then applying a dynamic program, Koutecký and Zink [31] improved this to $p_{\max }^{O(d^2)}{|I|}^{O(1)}$, still with the number of machines $M$ encoded in unary. Leveraging the huge-$n$-fold machinery, Knop et al. [27] get rid of the assumption on $M$ and obtain a $p_{\max }^{O(d^2)}{|I|}^{O(1)}$-time algorithm. Koutecký and Zink [31] pose the open question whether the dependency $p_{\max }^{O(d^2)}$ for the objective $Q\parallel C_{\max }$ can be improved, as it has been for identical machines. In a recent result, Rohwedder [37] gives an algorithm for $Q\parallel C_{\max }$ running in time $p_{\max }^{O(d)}{|I|}^{O(1)}.$ We note that our work has been compiled independently and prior to Rohwedders result, but we can leverage his novel ideas to reduce the value of $\mathrm{\Delta }$ to guarantee a similar result. Chen, Jansen and Zhang show that, for a given makespan $T$, there is no algorithm solving $P\parallel C_{\max }$ in time $2^{T^{1-\delta }}{|I|}^{O(1)}$ [6]. Jansen, Kahler and Zwanger extended these results to derive a lower bound of $p_{\max }^{O(d^{1-\delta })}{|I|}^{O(1)}$ [18]. As $Q\parallel C_{\max }$ is a generalization of $P\parallel C_{\max }$, these results extend to it.

Regarding the Closest String problem with $k$ input strings of length $L$, Gramm et al. [15] formulated the problem as an ILP of dimension $k^{O(k)}$. This led to an algorithm with running time $2^{2^{O(k\log (k))}}O(\log (L))$. Knop et al. [28] improved this double-exponential dependency to the currently best known algorithm with running time $k^{O(k^2)}O(\log (L))$. Rohwedder and Węgrzycki [38] showed that the Closest String problem (with binary alphabet) cannot be solved in time $2^{O(k^{2-\epsilon })}\text{poly}(L)$ with $\epsilon >0$ unless the ILP Hypothesis fails. The ILP Hypothesis states that for every $\epsilon >0$, there is no $2^{O(m^{2-\epsilon })}\text{poly}(L)$-time algorithm for ILPs with $\mathrm{\Delta }=O(1)$.

Imbalance is known to be NP-complete for various special graph classes [4, 23]. Fellows, Lokshtanov, Misra, Rosamond and Saurabh [13] showed that the problem is fixed-parameter tractable (FPT) parameterized by the size $k$ of the vertex cover. Their algorithm has a double exponential running time. There also exist FPT algorithms for this problem parameterized by other parameters, for instance imbalance [33], neighborhood diversity [2] and the combined parameter of treewidth and maximum degree [33]. Misra and Mittal [34] showed that Imbalance is in XP when parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest clique outside the twin cover.

A scheduling instance is defined by the number of jobs $n\in {\mathbb{Z}}_{\ge 0}^d$ with processing times $p\in {\mathbb{Z}}_{\ge 0}^d$ and the number of machines $m\in {\mathbb{Z}}_{\ge 0}^{\tau }$ with speed values $s\in {\mathbb{Z}}_{\ge 1}^{\tau }.$ This means that $N:={\Vert n\Vert }_1$ jobs of $d$ different sizes have to be scheduled on $M:={\Vert m\Vert }_1$ machines with ${\tau }_I$ different speeds. Since the processing times are integer, the total number of different job-types $d$ is bounded by $d\le p_{\max }.$ Each job has to be executed on a single machine.

Let $ℳ$ be the set of all machines. A schedule $\sigma :{\mathbb{Z}}_{\ge 0}^d\to ℳ$ is a mapping that assigns all jobs to the available machines. The load $L{(m^{(k)})}^{(\sigma )}$ of machine $m^{(k)}\in ℳ$ is the sum of the sizes of all jobs assigned to that machine by the schedule $\sigma .$ Assume $m^{(k)}$ has speed $s_k.$ Then we define the completion time of machine $m^{(i)}$ by $C{(m^{(i)})}^{(\sigma )}:=\frac{L{(m^{(i)})}^{(\sigma )}}{s_k},$ i.e., the time when machine $m^{(i)}$ has finished processing all jobs that were assigned to it by $\sigma .$

The objective functions that we consider in this work are:

• $\mathrm{■}$

  Makespan Minimization ($C_{\mathrm{𝐦𝐚𝐱}}$): ${\min }_{\sigma }\left({\max }_{m^{(i)}\in ℳ}C{(m^{(i)})}^{(\sigma )}\right)$

• $\mathrm{■}$

  Santa Claus ($C_{\mathrm{𝐦𝐢𝐧}}$): ${\max }_{\sigma }\left({\min }_{m^{(i)}\in ℳ}C{(m^{(i)})}^{(\sigma )}\right).$

When considering the Closest String problem, we are given a set of $k$ strings $S=\{s_1,\mathrm{\dots },s_k\}$ of length $L\in {\mathbb{Z}}_{\ge 1}$ from alphabet $[k]$ and an integer $d\in {\mathbb{Z}}_{\ge 0}$. The task is to find a string $c\in {[k]}^L$ of length $L$ (called the “closest string”) such that the Hamming distance $d_H(c,s_i)$ between $c$ and any string $s_i\in S$ is at most $d$. The Hamming distance for two equal-length strings is the number of positions at which they differ.

The input to the Imbalance problem is an undirected graph $G=(V,E)$ with $n$ vertices. An ordering of the vertices in $G$ is a bijective function $\pi =V\to [n]$. For $v\in V$, we define neighborhood of $v$ by $N(v):=\{u\in V\mid (u,v)\in E\}$, the set of left neighbors and the set of right neighbors . Note that $R(v)=N(v)\setminus L(v)$. The imbalance of at $v\in V$ is defined as ${\iota }_{\pi }(v)=||R(v)|-|L(v)||$ and the total imbalance of the ordering $\pi$ is $\iota (\pi )={\sum }_{v\in V}{\iota }_{\pi }(v)$. The aim is now to find an ordering $\pi$ that minimizes the total imbalance.