Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems

Very recently a major breakthrough has been occurred in the ILP complexity theory: based on the works [1, 2, 3] due to Dadush, Peikert & Vempala and [4] due to Regev & Stephens-Davidowitz, V. Reis and T. Rothvoss have proven in [5] that the problem Opt-IP can be solved in $\log(n)^{O(n)}\cdot\operatorname{poly}(\phi)$¹¹1The notation $\phi=\operatorname{size}(A,b,c)$ denotes the input bit-encoding length.-time beating the previous $O(n)^{n}\cdot\operatorname{poly}(\phi)$-time state of the art algorithm due to Dadush, Peikert & Vempala [1, 2]. Note that the complexity results of the works [5, 1, 2] are valid for even more general IP problems, where one needs to optimize a convex function defined by the subgradient oracle on a convex region defined by the strict hyperplane separation oracle. Surprisingly, due to Basu & Oertel [6], the ILP complexity in the oracle-model is $2^{O(n)}\cdot\operatorname{poly}(\phi)$. There exist some more general formulations of IP problems that allow polynomial algorithms in fixed dimension, see for example [7, 8, 9]. It is a long-standing open problem to provide a $2^{O(n)}\cdot\operatorname{poly}(\phi)$-time ILP algorithm.

The asymptotically fastest algorithm for the problem Count-IP in a fixed dimension can be obtained, using the approach of A. Barvinok [10] with modifications, due to Dyer & Kannan [11] and Barvinok & Pommersheim [12]. A complete exposition of Barvinok’s approach can be found in [13, 12, 14, 15, 16], additional discussions and connections with "dual"-type counting algorithms could be found in the book [17], due to J. Lasserre. An important notion of the half-open sign decomposition and other variants of Barvinok’s algorithm that is more efficient in practice is given by Köppe & Verdoolaege in [18]. The paper [14] of Barvinok & Woods gives important generalizations of the original techniques and adapts them to a wider range of problems to handle projections of polytopes. Using the fastest deterministic Shortest Lattice Vector Problem (SVP) solver by Micciancio & Voulgaris [19], the computational complexity of Barvinok’s algorithm can be upper bounded by

Here we can parameterize by $\nu$, because any polyhedron can be transformed to an integer-equivalent simple polyhedron, using a slight perturbation of the r.h.s. vector $b$ (see, for example, Theorem 9, due to Megiddo & Chandrasekaran [20] and Remark 3). Let us assume that $\operatorname{\mathcal{P}}$ is defined by the form Canon-Form. Due to the seminal work of P. McMullen [21], the number of vertices attains its maximum at the class of polytopes, which is dual to the class of cyclic polytopes. Together with the formula from [22, Section 4.7] for the number of facets of a cyclic polytope, it follows that the maximum number of vertices in an $n$-dimensional polyhedron with $m$ facets is bounded by

Therefore, $\nu\leq\xi(n,m)$ and $\nu=O(m/n)^{n/2}$. Due to [23, Chapter 3.2, Theorem 3.2], we have $\Delta=2^{O(\phi)}$. Using the notation $\phi$, the bound (4) becomes

which gives a polynomial-time algorithm in a fixed dimension for the problem Count-IP.

The papers [24, 25, 26, 27] deal with the parameter $\Delta$ to give pseudo-polynomial algorithms, which will be more effective in a varying dimension. Recently, it was shown by Gribanov and Malyshev in [25] that the Count-IP problem can be solved with an algorithm whose computational complexity is polynomial in $\nu$, $n$, and $\Delta$. Unfortunately, the paper [25] contains an inaccuracy, which makes its main conclusion incorrect. This inaccuracy was eliminated in [28]. The main result of [28] (and [25]) is represented by the following

We improve the last result in Theorem 2 of our paper, and it will be our main tool for sparse problems. A fully self-contained proof of this theorem will be given in Subsection 6.3. Wherever it will be necessary to refer to the original article with an inaccuracy, we will cite the full proof of the relevant statement in Appendix.

Using Theorem 1 and different ways to estimate $\nu$, the paper [25] gives new interesting arithmetic complexity bounds for the Feasibility-IP and Count-IP problems. Let us present them, taking into account the improvement made in the Theorem 2:

• •

  The bound

  $$O\Bigl{(}\frac{m}{n}\Bigr{)}^{n}\cdot n^{4}\cdot\Delta^{3}$$

  for systems in the form Canon-Form that is polynomial in $m$ and $\Delta$, for any fixed $n$. In comparison with the bound (5), this bound has a much better dependence on $n$, considering $\Delta$ as a parameter. For example, taking $m=O(n)$ and $\Delta=2^{O(n)}$, the above bound becomes $2^{O(n)}$, which is even faster, than the state of the art algorithm for the problem Feasibility-IP, due to Reis & Rothvoss [5], with the complexity bound $\log(n)^{O(n)}\cdot\operatorname{poly}(\phi)$;

• •

  The general bound, for systems in the canonical or the standard forms,

  $$O(n)^{4+n}\cdot\Delta^{3+2n}$$

  that is polynomial on $\Delta$, for any fixed $n$;

• •

  The bound

  $$O\bigl{(}n/k\bigr{)}^{2k}\cdot n^{4}\cdot\Delta^{3}$$

  (6)

  for systems in the form Standard-Form, which is also valid for systems in the form Canon-Form with $k=m-n$, that is polynomial on $n$ and $\Delta$, for $k=O(1)$. Taking $k=1$, it gives an $O\bigl{(}n^{6}\cdot\Delta^{3}\bigr{)}$-algorithm to compute the number of integer points in a simplex. The last result can be used to count solutions of the Unbounded Subset-Sum problem, which is formulated as follows. Given numbers $w_{1},\dots,w_{n}$ and $W$, we need to count the number of ways to exchange the value $W$ by the values $w_{i}$, assuming that each value $w_{i}$ can be used unlimitedly. It can be done by algorithms with the arithmetic complexity bound

  $$O(n^{6}\cdot w_{\max}^{3}).$$

  Moreover, this result can be used to handle the $k$-dimensional variant of the Unbounded Subset-Sum problem, when the costs $w_{i}$ and $W$ are represented by $k$-dimensional vectors. Using the Hadamard’s bound, it gives the following arithmetic complexity bound:

  $$O(n)^{2(k+2)}\cdot k^{-k/2}\cdot w_{\max}^{3k},$$

  where $w_{\max}=\max_{i}\|w_{i}\|_{\infty}$. Note that the earlier paper of Lasserre & Zeron [29] also gives a counting FPT-algorithm for the Unbounded Subset-Sum problem, parameterized by $w_{\max}$, but an exact complexity bound was not given.

In the current work, we try to estimate the value of $\nu$ in a different way, to handle ILP problems with sparse matrices. Additionally, we generalize Theorem 2 to work with the problem Opt-And-Count-IP. The resulting theorem is the following:

The theorem’s proof is given in Subsection 6.5. This new complexity bounds, applied to the problems in the form Canon-Form, are emphasized in Table 2. As the reader could see, with respect to the problem Feasibility-IP, under the assumptions $\gamma_{1,\infty}\leq\log^{\varepsilon}(n)$ or $\|A\|_{\max}\leq\log^{\varepsilon}(n)$ and $\operatorname{\overline{\operatorname{ts}}}\leq\log^{\varepsilon}(n)$, for some $\varepsilon>0$, our complexity bounds outperform the state of the art complexity bound $\log(n)^{O(n)}\cdot\operatorname{poly}(\phi)$. With respect to the problem Count-IP, under the assumption $\|A\|_{\max}=n^{o(\log(n))}$, our complexity bounds outperform the state of the art complexity bound $O(m/n)^{n/2}\cdot\phi^{n\log(n)}$.

The following corollary, which is a straightforward consequence of Theorem 3, shows that, under some assumptions, the Count-IP and Opt-And-Count-IP problems can be solved by a faster algorithm than the complexity bound (5) gives.

In this subsection, we consider ILP problems in the form Standard-Form. Since in our definition $k=\operatorname{rank}(A)$, it is essential to call the parameter $k$ as the co-dimension of $\operatorname{\mathcal{P}}$. We are interested in the complexity bounds for bounded values of $k$. Let us survey some remarkable results. The following result, due to Gribanov et al. [26, see Theorem 8 and Corollary 9], gives a parameterization by $k$ and $\Delta$.

As it was noted in [26], due to [38], we can assume that $\eta=O(\log(k))^{k}$, and the previous complexity bound becomes

For the case when $A$ only has non-negative elements, the basic dynamic-programming scheme from [39] can be used to derive an algorithm, parameterized by $\|b\|_{\infty}$ and $k$. Using fast $(\min,+)$-convolution algorithms (see, for example, [40] or [41]), the same complexity bound can be used for systems in the Standard-Form form with box constraints. We emphasize it in the following statement:

Due to the works [42] and [43] of Cunningham & Geelen and Fomin et al., the parameter $k$ in the term $\bigl{(}\|b\|_{\infty}+1\bigr{)}^{k}$ can be replaced by stronger parameters $2\omega$ or $\rho+1$, where $\omega$ is the branch-width and $\rho$ is the path-width of the column matroid of $A$.

The approach, which is most important for us in this Subsection, is based on the notion of the hereditary discrepancy of $A$.

The paper [44], due to Jansen and Rohwedder, gives a powerful ILP algorithm, parameterized by $\operatorname{herdisc}(A)$ and $k$, which will be our second main tool.

Different bounds on $\operatorname{herdisc}(A)$ can be used to develop different complexity bounds for ILP problems. Due to the works [45] and [46] of Lovász, Spencer, & Vesztergombi, and Spencer, it is known that

Due to Beck and Fiala [47], the value of $\operatorname{herdisc}(A)$ is bounded by the $l_{1}$-norm of columns. More precisely,

Additionally, Beck and Fiala conjectured that $\operatorname{herdisc}(A)=O\bigl{(}\sqrt{\|A\|_{\infty}}\bigr{)}$ and settling this has been an elusive open problem. The best known result in this direction is due to Banaszczyk [48]:

The important matrix characteristic that is closely related to $\operatorname{herdisc}(A)$ is $\operatorname{detlb}(A)$. Due to Lovász, Spencer, & Vesztergombi [45], it can be defined as follows:

and it was shown in [45] that $\operatorname{herdisc}(A)\geq(1/2)\cdot\operatorname{detlb}(A)$. Matoušek in [49] showed that $\operatorname{detlb}(A)$ can be used to produce tight upper bounds on $\operatorname{herdisc}(A)$. The result of Matoušek was improved by Jiang & Reis in [50]:

Next, let us consider the problems Count-IP and Opt-And-Count-IP. Clearly, the number of vertices in a polyhedron, defined by a system in the Canon-Form, can be estimated by $\binom{n}{k}=O(n/k)^{k}$. The last fact in combination with Theorem 2 results in the following corollary, which gives a parameterization by $\Delta$ and $k$.

The next theorem considers the ILP problems in the standard form with sparse $A$. In this theorem, we just summarize the combinations of Theorem 5 with the different bounds on $\operatorname{herdisc}(A)$. Additionally, we use Corollary 2 to solve the counting-type problems. Note that the $5$-th complexity bound of the next theorem has already been proven in [44], we put it here for the sake of completeness.

Finally, before we will finish the current section, let us consider ILP problems in the form Standard-Form with box constraints. Using the basic dynamic programming scheme from [51], combined with a linear-time algorithm for the $(\min,+)$-convolution (see, for example, [26, Theorem 7], [40] or [41]), it is easy to prove the following proposition.

Different bounds on $\chi$ give different algorithms, based on Proposition 2. The paper [51] of Eisenbrand & Weismantel gives $\chi\leq k\cdot\bigl{(}2k\cdot\|A\|_{\max}+1\bigr{)}^{k}$. The paper [52], due to Lee, Paat et al., gives $\chi\leq(2k+1)^{k}\cdot\Delta$. Recent result of Lee, Paat et al. [53] states that