Abstract 1 Introduction 2 Reductions 3 Algorithm for few distinct variables References

Fine-Grained Equivalence for Problems Related to Integer Linear Programming

Lars Rohwedder ORCID University of Southern Denmark (SDU), Odense, Denmark Karol Węgrzycki ORCID Saarland University, Saarbrücken, Germany
Max Planck Institute for Informatics, Saarbrücken, Germany
Abstract

Integer Linear Programming with n binary variables and m many 0/1-constraints can be solved in time 2O~(m2)poly(n) and it is open whether the dependence on m is optimal. Several seemingly unrelated problems, which include variants of Closest String, Discrepancy Minimization, Set Cover, and Set Packing, can be modelled as Integer Linear Programming with 0/1 constraints to obtain algorithms with the same running time for a natural parameter m in each of the problems. Our main result establishes through fine-grained reductions that these problems are equivalent, meaning that a 2O(m2ε)poly(n) algorithm with ε>0 for one of them implies such an algorithm for all of them.

In the setting above, one can alternatively obtain an nO(m) time algorithm for Integer Linear Programming using a straightforward dynamic programming approach, which can be more efficient if n is relatively small (e.g., subexponential in m). We show that this can be improved to nO(m)+O(nm), where n is the number of distinct (i.e., non-symmetric) variables. This dominates both of the aforementioned running times.

Keywords and phrases:
Integer Programming, Fine-Grained Complexity, Fixed-Parameter Tractable Algorithms
Funding:
Lars Rohwedder: Supported by Dutch Research Council (NWO) project “The Twilight Zone of Efficiency: Optimality of Quasi-Polynomial Time Algorithms” [grant number OCEN.W.21.268].
Karol Węgrzycki: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979).
Copyright and License:
[Uncaptioned image] © Lars Rohwedder and Karol Węgrzycki; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Design and analysis of algorithms
Related Version:
Full Version: https://arxiv.org/abs/2409.03675
Acknowledgements:
We thank Friedrich Eisenbrand for his valuable insights and constructive discussions that enhanced this work.
Editors:
Raghu Meka

1 Introduction

The study of parameterized complexity for Integer Linear Programming has a long history: classical works by Lenstra [15] and Kannan [12] and very recently Rothvoss and Reis [19] provide FPT algorithms in the number of variables n of an ILP of the form Axb,xn. In an orthogonal line of research, Papadimitriou [17] gave an FPT algorithm in the number of constraints and the size of the coefficients of A and b for an ILP in the standard form Ax=b,x0n. Interest in the second line of work has been renewed by the improved algorithms due to Eisenbrand, Weismantel [9] and Jansen, Rohwedder [11], which give essentially optimal running times (mΔ)O(m)poly(n) due to a conditional lower bound based on the Exponential Time Hypothesis (ETH) [14]. Here, Δ is the maximum absolute size of an entry in A. The work by Eisenbrand and Weismantel also considers a version where variables are subject to box-constraints, which will be the primary focus of this work, see the definition below.

Integer Linear Programming Input: Constraint matrix A{Δ,,Δ}m×n, right-hand side bm, variable bounds ,u0n. Task: Find xn with Ax =b i xiui i=1,2,,n.

We refer to the variant where =(0,,0)𝖳 and u=(1,,1)𝖳 as binary Integer Linear Programming.

Binary Integer Linear Programming Input: Constraint matrix A{Δ,,Δ}m×n, right-hand side bm. Task: Find x{0,1}n with Ax =b.

The running times obtained in [9] for either variant is (mΔ)O(m2)poly(n). Also for matrices with only 0/1 coefficients nothing better than 2O~(m2)poly(n) is known. It is an intriguing question whether the slightly unusual exponent of O~(m2) is necessary, which is in the spirit of fine-grained complexity. Since the dominant complexity-theoretic assumption of PNP is not powerful enough to show precise lower bounds on running times, the field of fine-grained complexity is concerned with finding lower bounds via stronger conjectures, see e.g.,  [2, 20, 6]. A number of such conjectures exist by now, often with interesting connections between them. Even if one doubts these conjectures, the reductions still provide insights into how problems relate to each other.

Based on existing conjectures, the best lower bound known on the exponent of Integer Linear Programming is Ω(mlogm) from the easier unbounded setting [14], which is of course not tight in this setting. In this paper, we take another path: we assume that Integer Linear Programming cannot be solved faster than the state-of-the-art and present several other natural parameterized problems that are all equivalent with respect to improvements on their running time.

Hypothesis 1 (ILP Hypothesis).

For every fixed ε>0, there is no 2O(m2ε)poly(n) time algorithm for Integer Linear Programming with Δ=O(1).

In all of the problems below, the symbol m is chosen for the parameter of interest.

Closest String with Binary Alphabet Input: Alphabet Σ={0,1}, strings s1,s2,,smΣn Task: Find string tΣn minimizing maxid(t,si), where d(t,si) is the Hamming distance between t and si, i.e., the number of positions the two strings differ in.

We refer to the generalization with arbitrary Σ simply as Closest String.

Discrepancy Minimization Input: Universe U={1,2,,n}, set system S1,S2,,SmU Task: Find coloring χ:U{1,1} minimizing maxi|uSiχ(u)|.

Set Multi-Cover Input: Universe U={1,2,,m}, set system S1,S2,,SnU, b Task: Find I{1,2,,n} of minimal cardinality such that for each vU there are at least b sets Si with iI and vSi.

Set Multi-Packing Input: Universe U={1,2,,m}, set system S1,S2,,SnU, b Task: Find I{1,2,,n} of maximal cardinality such that for each vU there are at most b sets Si with iI and vSi.

Many of these problems are well-known applications of ILP techniques. For example, Knop et al. [13] provided mO(m2)poly(n) algorithms for Closest String and Set Multi-Cover. Discrepancy Minimization is usually considered within the context of approximation algorithms (see, e.g., [3]).

As mentioned above, our main result is the following equivalence.

Theorem 2.

The following statements are equivalent:

  1. (1)

    There exists an 2O(m2ε)poly(n) algorithm for Integer Linear Programming with Δ=O(1) with ε>0.

  2. (2)

    There exists an 2O(m2ε)poly(n) algorithm for Binary Integer Linear Programming with A{0,1}m×n and nmO(m) with ε>0.

  3. (3)

    There exists an 2O(m2ε)poly(n) algorithm for Closest String with Binary Alphabet with ε>0.

  4. (4)

    There exists an 2O(m2ε)poly(n) algorithm for Discrepancy Minimization with ε>0.

  5. (5)

    There exists an 2O(m2ε)poly(n) algorithm for Set Multi-Cover with ε>0.

  6. (6)

    There exists an 2O(m2ε)poly(n) algorithm for Set Multi-Packing with ε>0.

Note that Item 1 is the negation of 1. All problems in Theorem 2 are easily transformed into the first problem, i.e., Integer Linear Programming with Δ=O(1), while maintaining the same value of m. Hence, the more interesting aspect of the theorem is that all these problems are as expressive as the first one.

1 considers Integer Linear Programming with relatively small entries, i.e., Δ=O(1). One can also ask the question of whether there is any parameter regime for Δ for which the state-of-the-art can be improved. In this spirit, a stronger variant of the conjecture is the following.

Hypothesis 3 (Strong ILP Hypothesis).

For every fixed ε>0 and δ0, there is no 2O(mδ+2ε)poly(n) time algorithm for Integer Linear Programming with Δ=2mδ.

Note that 1 is a special case of 3 for δ=0. Another interesting regime is the complexity of Integer Linear Programming with Δ=2m, because of a connection to block-structure integer programming, which we elaborate on later. There, the state-of-the-art algorithm requires time mO(m3)poly(n), Integer Linear Programming with large entries can be reduced to an equivalent instance with a 0/1 matrix as seen in the following theorem, but the reduction is not strong enough to show equivalence between the two hypotheses.

Theorem 4.

There is a polynomial time algorithm that transforms an instance of Integer Linear Programming with Δ>1 into an equivalent one with A{0,1}m×n for m=O(mlogΔ) and nmO(m).

This implies that if there is an algorithm with running time 2O(m1.5ε)poly(n) for Integer Linear Programming with A{0,1}m×n, then there is a 2O(m3ε)poly(n) time algorithm for Integer Linear Programming with Δ=2m.

One might hope to improve the theorem to m=O(mlogΔ), since then a 2O(m2ε)poly(n) time algorithm for 0/1 matrices would imply a 2O(m3ε)poly(n) time algorithm for Δ=2m. However, such a reduction would imply the strong result that under ETH is equivalent to 1. This is because under ETH the Subset Sum problem, i.e., the case when m=1, cannot be solved in Δo(1)poly(n) time  [1] and the hypothetical reduction would be able to encode an instance of Subset Sum into an ILP with m=O(logΔ). We are not aware of any meaningful reduction in the other direction, i.e., from large m and small Δ to smaller m and larger Δ. It is possible to aggregate m constraints into a single one with entries bounded by Δ=ΔO(m2), but this reduction seems useless since the resulting parameter range requires poly(Δ)poly(n) time due to the ETH lower bound mentioned above.

Assuming 3, we derive a tight lower for a form of block-structured integer linear programs that has been studied extensively in recent literature. For simplicity, we consider here the basic setting with m×m submatrices.

n-Fold Integer Linear Programming Input: Square matrices A1,,An,B1,,Bn{Δ,,Δ}m×m, right-hand sides b(0),,b(n)m. Task: Find x(1),,x(n)0m with A1x(1)++Anx(n) =b(0) B1x(1) =b(1) Bnx(n) =b(n)

Theorem 5.

For every δ>0, there is no algorithm with running time 2O(m3δ)poly(n) for n-Fold Integer Linear Programming when the maximum absolute entry is bounded by Δ=O(1), unless 3 is false.

This matches the best algorithms known for the problem, see [5] and references therein. The reduction follows the same idea as used in [10], where the authors show a non-tight quadratic lower bound for the exponent based on ETH. Our lower bound is stronger simply because the conjecture we base it on is stronger.

1.1 Tightness of more general problems

There are several other, more general problems to the ones mentioned above, for which known algorithms would be tight assuming that one cannot improve the running time for the class of problems in Theorem 2. However, we do not know if these are all equivalent.

The algorithm by Eisenbrand and Weismantel [9] also works for the optimization version of ILP, i.e.,

maxc𝖳x,Ax=b,xu,xn.

This leads to the same running time of (mΔ)O(m2)poly(n) except for a slightly higher constant in the exponent. Notably, the coefficients of c do not increase the number of arithmetic operations.

Given a matrix A{Δ,,Δ}m×n and a convex function g:m{}, Dadush, Léonard, Rohwedder, and Verschae [7] have shown that one can find the minimizer of g(Ax),x{0,1}n in time (mΔ)O(m2)poly(n) (assuming polynomial time to evaluate g). This problem is a generalization of Binary Integer Linear Programming, since one can take g(b)=0 if b=b and g(b)= otherwise.

Given a linear matroid M=(E,), where |E|=n, a matrix A{Δ,,Δ}n×m and a right-hand side bm, Eisenbrand, Rohwedder, and Węgrzycki [8] gave an algorithm that finds a basis B of M such that AxB=b in time O(mΔ)O(m2)poly(n), where xB is the incidence vector of B. This generalizes Binary Integer Linear Programming, since one can take E as the set of binary variables and n additional dummy variables and then take M as the uniform matroid of rank n.

Finally, Closest String (with arbitrary alphabet) can still be solved in time mO(m2)poly(n) for example by casting it as the previous matroid problem [8] or as a block structured ILP, see [13].

1.2 Algorithm for few distinct variables

We show that the running time of 2O~(m2)poly(n) for Integer Linear Programming with Δ=O(1), i.e., the subject of 1, can be improved if the number of distinct variables is low. For the sake of generality, we state the algorithmic result for the optimization variant and any range of Δ.

Theorem 6.

Consider the integer programming problem

max c𝖳x
Ax =b (1)
ixi ui i=1,,n
x n.

Let Δ be an upper bound on the absolute value of entries of A. The problem (1) can be solved in time

nm+1O(mΔ)mlog(u).

Using standard reductions, see e.g. Section 2.5.2, one may reduce u to (mΔ)O(m), making the logarithmic factor insignificant.

We will now interpret this running time and point out interesting special cases.

Binary ILP with 𝑨{𝟎,𝟏}𝒎×𝒏

Here, the running time above implies an nO(m)+O(nm) time algorithm, where n is the number of distinct variables, i.e., variables that differ either in their entry of c or in their column of A: one can merge identical variables in time 2O(m)+O(nm) time, after which un. Furthermore, without loss of generality, the rows of A are linearly independent, thus mn. Hence, the overall running time is

2O(m)+O(nm)+nm+1O(m)mlogn nO(m)logn+O(nm)
nO(m)+O(nm).

Here, the last inequality follows from a case distinction whether logn is greater than nO(m) or not. Note that in the setting without objective function we have n2m. Thus, this running time is at least as good as the known 2O~(m2)poly(n) time algorithms. It also dominates the running time of nO(m) one would get by simple dynamic programming over the right-hand sides b that are feasible (for which there can be at most nm).

Binary ILP with 𝑨{𝟎,𝟏}𝒎×𝒏 and a constant number of 𝟏s in each column

Here, the number of distinct columns is polynomial in m and the previous case implies a running time of mO(m)+O(nm), meaning that 1 does not extend to this special case.

2 Reductions

The basic idea of all reductions for Theorem 2 is that we transform one problem with parameter m into another problem with parameter m=O(mlogO(1)m). Additionally the size of the instance may only increase from n to 2O(m2δ)poly(n) for some δ>0. The concrete reductions we prove can be seen in Figure 1.

Figure 1: Overview of reductions in this paper.

2.1 Closest String

Let d be the bound on the maximum hamming distance in the decision version of Closest String with Binary Alphabet. For a string sΣn we denote by s[i] the ith character. For ij we write s[ij] for the substring from the ith to the jth character.

Lemma 7.

Theorem 2, Statement 1 implies Statement 3

Proof.

The following is an ILP model for Closest String with Binary Alphabet.

i=1nxi𝟙{sj[i]=0}+(1xi)𝟙{sj[i]=1} d for all j{1,2,,m}
x {0,1}n

One may add slack variables to turn the inequalities into equalities.

Lemma 8.

Theorem 2, Statement 3 implies Statement 2

Proof.

We want to transform the following ILP

Ax =b (2)
x {0,1}n

where A{0,1}m×n, into an equivalent instance of Closest String. We first rewrite (2) into a more convenient form.

Claim 9.

One can in polynomial time construct a matrix C{1,1}(2m+2)×2n and some c2m+2 such that (2) is feasible if and only if there is a solution to

Cx c (3)
x {0,1}2n.

Furthermore, every feasible x for (3) has x1++x2n=n.

This follows from simple transformations. We defer the proof until later and first show how the reduction follows from it. By comparing to the ILP formulation of Closest String we observe that (3) corresponds to a “non-uniform” variant of Closest String. It can be reformulated as: given strings s1,,s2m+2{0,1}2n and bounds d1,,d2m+2, find a string t{0,1}2n such that for each j=1,,m we have d(t,sj)dj. This follows from the ILP model given in the proof of Lemma 7. Furthermore, we have the guarantee that any solution has exactly n ones. To transform this into a regular instance, we add two more strings r1,r2 and to each string sj we add 4n more characters, which makes a total of 6n characters per string. The strings of this instance s1,,s2m+2,r1,r2 are defined as

r1=( 0,,0, 0,,0, 0,,0, 0,,0 ),
r2=( 1,,1, 1,,1, 1,,1, 0,,0 ),
sj=( sj2n chars, 1,,1n chars,0,,0n chars, ​​​​ 1,,1,2ndj chars0,,0dj chars ).

Here, we assume without loss of generality that dj{0,,2n}. We claim that there is a solution to this instance with maximum Hamming distance 2n if and only if there is a solution to the non-uniform instance.

Claim 10.

If there is a string t{0,1}6n with distance at most 2n to r1,r2, and sj, j=1,2,,2m+2, then there is also a string t{0,1}2n with distance at most dj to sj, j=1,2,,2m+2.

Claim 11.

If there is a string t{0,1}2n with distance at most dj to sj, j=1,2,,2m+2, then there is also a string t{0,1}6n with distance at most 2n to r1,r2, and sj, j=1,2,,2m+2.

From these claims, the lemma follows immediately.

Proof of 9.

We add variables x¯1,,x¯n and force a solution to take exactly n many ones

Ax =b
x1++xn+x¯1++x¯n =n
x,x¯ {0,1}n.

Next, we change the equality constraints into inequalities and A into a 1,1 matrix

Ax𝟏x¯ b
Ax+𝟏x¯ b
x1++xn+x¯1++x¯n n
x1xnx¯1x¯n n
x,x¯ {0,1}n

where A=2A𝟏 with 𝟏 being the all-ones m×n matrix and b=2b(n,,n)𝖳.

Proof of 10.

Suppose there is a string t{0,1}6n with distance at most 2n to each of the strings s1,,s2m+2,r1,r2. Because d(r1,r2)=4n, string t must match r1 and r2 on characters where r1 and r2 match. More precisely, t[i]=0 for i{4n,,6n}. Formally, this follows because of

4n d(t,r1)+d(t,r2)
=d(t[14n],r1[14n])+d(t[14n],r2[14n])
+2d(t[4n+16n],(0,,0))
d(r1[14n],r2[14n])+2d(t[4n+16n],(0,,0))
4n+2d(t[4n+16n],(0,,0)).

Let us now analyze the distance between t:=t[12n] and sj for some j. Since the last 2n characters of t are zero, we have d(t[4n+16n],sj[4n+16n])=2ndj. Thus,

d(t,sj) d(t,sj)d(t[4n+16n],sj[4n+16n])
2n(2ndj)=dj.

Thus, string t is a solution for the non-uniform instance.

Proof of 11.

Let t{0,1}2n with d(t[12n],sj)dj for all j. We extend it to a string t{0,1}6n by setting t[12n]=t, t[2n+13n]=(1,,1), and t[3n+16n]=(0,,0). Let us now verify that t has a distance at most 2n to each string. For r1,r2 note that t[12n] has exactly n ones by guarantee of the non-uniform instance. Thus, the distance to r1 and r2 is exactly 2n. Consider some j{1,,2m+2}. Then

d(sj,t)=d(sj,t[12n])+2ndj2n.

2.2 Discrepancy Minimization

Lemma 12.

Theorem 2, Statement 1 implies Statement 4

Proof.

Let d be a bound on the objective in the decision version of Discrepancy Minimization. Let A be the incidence matrix of the given set system. Then the colorings of discrepancy at most d are exactly the solutions of

(AA)y (ddd)
y {1,1}n.

This can be equivalently formulated as

(2A2A)x (AA)(111)+(2d2d2d)
x {0,1}n.

where xi=(1+yi)/2. One may translate the inequalities into equalities by introducing slack variables. Therefore, an algorithm for Integer Linear Programming can be used to solve Discrepancy Minimization.

Lemma 13.

Theorem 2, Statement 4 implies Statement 2.

Proof.

Consider an ILP of the form

Ax =b (4)
x {0,1}n

for A{0,1}m×n and nmO(m). We will construct an instance of Discrepancy Minimization which has discrepancy zero if and only if the ILP has a feasible solution. Towards this, we first reformulate the ILP above as

Ay =b (5)
y {1,1}n

where b=2bA(1,,1)𝖳. Note that x is feasible for (4) if and only if y=2x(1,,1)𝖳 is feasible for (5). Also, if b=(0,,0)𝖳, then (5) is already equivalent to an instance of Discrepancy Minimization that tests for discrepancy zero. To handle the general case, we transform it into an equivalent system with right-hand size (0,,0)𝖳. We first construct a gadget of elements that have the same color.

Claim 14.

For any k we can construct a pair of matrices B,B¯{0,1}(2k1)×2k such that there are exactly two solutions to

Bz+B¯z¯ =(00)
z,z¯ {1,1}2k

namely z=(1,,1)𝖳,z¯=(1,,1)𝖳 and z=(1,,1)𝖳,z¯=(1,,1)𝖳.

We will defer the proof to the end of the section. Using this gadget with k=log2n=O(mlogm) we now replace each coefficient bj in the previous system by the variables from the gadget. Note that (5) is infeasible if b>n. Thus assume without loss of generality that bn2k. Let C,C¯{0,1}2k×m be defined as follows. The jth row of C has bj many ones at arbitrary positions if bj0 and is all zero otherwise; contrary, the jth row of C¯ has bj many ones at arbitrary positions if bj<0 and is all zero otherwise.

Now consider the system

Ay+Cz+C¯z¯ =(00)
Bz+B¯z¯ =(00) (6)
y {1,1}n
z,z¯ {1,1}2k.

We claim that (6) has a solution if and only if there is a solution to (5). Let y,z,z¯ be a solution to the former. Notice that the negation of a solution is also feasible. Due to 14 we may assume without loss of generality that z=(1,,1)𝖳 and z¯=(1,,1)𝖳, negating the solution if necessary. It follows that

Cz+C¯z¯=b.

Thus, Ay=b, which concludes the first direction. For the other direction, assume that there is a solution y to (5). We set z=(1,,1)𝖳, z¯=(1,,1)𝖳, which by 14 satisfies Bz+B¯z¯=(0,,0)𝖳. As before we have that Cz+C¯z¯=b. Thus, y,z,z¯ is a solution to (6). This establishes the equivalence of the initial ILP instance to (6), which corresponds to an instance of Discrepancy Minimization where we test for discrepancy zero with m=O(mlogm) sets.

Proof of 14.

The existence of such a matrix can be proven by induction: for k=1, we simply take B=B¯=(1). Now suppose that we already have a pair of matrices B,B¯{0,1}(2k1)×2k as above. Then we set

B=(B011000011) and B¯=(B¯000111100){0,1}(2k+1)×22k.

It can easily be checked that choosing either z=z=(1,,1)𝖳,z¯=z¯=(1,,1)𝖳 or z=z=(1,,1)𝖳,z¯=z¯=(1,,1)𝖳 satisfies

B(zz)+B¯(z¯z¯)=(00). (7)

Now take any z,z,z¯,z¯{1,1}2k+1 that satisfy (7). Then we have that Bz+B¯z¯=(0,,0)𝖳. Hence by induction hypothesis either z=(1,,1)𝖳,z¯=(1,,1)𝖳 or z=(1,,1)𝖳,z¯=(1,,1)𝖳. Assume for now the first case holds. Then because of the second-to-last rows of B,B¯ we have

2k+i=12kz¯i=i=12kzi+z¯i=0.

Hence, z¯=(1,,1)𝖳=z¯. Similarly, the last row of B,B¯ implies that z=(1,,1)𝖳=z. Analogously, if z=(1,,1)𝖳,z¯=(1,,1)𝖳 then z=z and z¯=z¯.

2.3 Set Multi-Cover

Lemma 15.

Theorem 2, Statement 1 implies Statement 5.

Proof.

An instance of the decision version of Set Multi-Cover with a bound d on the cardinality can be formulated as

x1++xn d
Ax (bb)
x {0,1}n

where A{0,1}m×n is the incidence matrix of the given set system. This can easily be translated to the form of (1) by introducing slack variables. Notice that this ILP has m+1 constraints. Thus, a faster algorithm for ILP would imply a faster algorithm for Set Multi-Cover.

In the remainder, we show that the converse is also true.

Lemma 16.

Theorem 2, Statement 5 implies Statement 2.

Proof.

First, we reduce to a “non-uniform” version of Set Multi-Cover where each element v has a different demand bv. Let A{0,1}m×n and b0m and consider the solutions to

Ax =b
x {0,1}n.

First, we add n additional binary variables x¯ and the requirement that exactly n variables are equal to one, i.e.,

Ax =b
x1++xn+x¯1++x¯n =n
x {0,1}n
x¯ {0,1}n.

This system is equivalent to the previous one, by setting nx1xn arbitrary variables x¯i to 1. Next, we transform the equality constraints Ax=b into inequalities:

Ax b
(𝟏A)x+𝟏x¯ (nn)b
x1++xn+x¯1++x¯n =n
x {0,1}n
x¯ {0,1}n.

Here, 𝟏 denotes the n×n all-ones matrix. Note that the second constraint is equivalent to Axb, since we fixed the number of ones in the solution. This ILP is feasible if and only if the optimum of the following ILP is n.

min x1++xn+x¯1++x¯n
Ax b
(𝟏A)x+𝟏x¯ (nn)b
x1++xn+x¯1++x¯n n
x {0,1}n
x¯ {0,1}n.

This ILP corresponds to an instance of non-uniform Set Multi-Cover with 2m+1 elements.

To reduce a non-uniform instance S1,,Sn, (bv)vU, to a uniform instance of Set Multi-Cover we proceed as follows: add one new element and n many new sets to the instance. The coverage requirement of each element is n. The new element is contained in each of the new sets and in none of the old ones. Thus, each new set has to be taken. Furthermore, we add each old element v to nbv many arbitrary new sets.

2.4 Set Multi-Packing

Lemma 17.

Theorem 2, Statements 5 and 6 are equivalent.

Proof.

Notice the following duality between Set Multi-Cover and Set Multi-Packing. Let U={1,2,,m}, S1,S2,,Sn, and b be an instance of Set Multi-Cover. Now consider the instance of Set Multi-Packing with universe U, set system S¯1=US1,S¯2=US2,,S¯n=USn, and bounds b¯=nb. This is a bipartition between instances of Set Multi-Cover and Set Multi-Packing, i.e., it can be performed in both ways.

For one pair of such instances, a solution I for Set Multi-Cover is feasible if and only if I¯={1,2,,n}I is feasible for Set Multi-Packing. Thus, if the optimum of Set Multi-Cover is k, then the optimum of Set Multi-Packing is nk.

2.5 Integer Linear Programming

In this section, we prove Theorem 4, i.e., we show how to reduce an ILP with large coefficients into a (larger) ILP with only 0/1 coefficients.

See 4

Furthermore, we show how to reduce an ILP with arbitrary upper and lower bounds into one with at most (mΔ)O(m) binary variables. Note that this implies that Statements 1 and 2 are equivalent and concludes the proof of Theorem 2.

2.5.1 From large coefficients to zero-one

We will transform an ILP of the form

Ax =b
x u
x n

where A{Δ,,Δ}m×n into an equivalent one with A{0,1}m×n for m=O(mlogΔ). Let k=log2(Δ). For the jth row of A we introduce 4(k+1) rows in A, denoted by r0+(j),r0+(j),,rk+(j),rk+(j),r0(j),r0(j),,rk(j),rk(j). Intuitively, the rows ri+(j),ri+(j) are symmetric rows that each stand for a value of 2i in row j. Similarly, ri(j),ri(j) stand for a value of 2i in row j. The right-hand sides of the new ILP are bj for row r0+(j) and zero for all other rows affiliated with j.

For each column Ai we derive a column of A as follows: for row j we consider the binary encoding of Aji and have the column in A use this binary encoding in r0+(j),r1+(j),,rk+(j) if Aji0 and in r0(j),r1(j),,rk(j) if Aji<0. All other entries of this column are zero.

We now add auxiliary variables to shift the values from one power to another. For each row j and each i=0,,k1 we add:

  • a variable x(i,j) with a one in row ri+(j),ri+(j) and ri+1(j) and

  • a variable x¯(i,j) with a one in row ri(j),ri(j) and ri+1+(j).

Furthermore, for each row j and each i=0,,k we add:

  • a variable xa(i,j) with a one in row ri+(j) and ri(j),

  • a variable xb(i,j) with a one in row ri(j) and ri+(j), and

  • a variable xc(i,j) with a one in row ri(j) and ri+(j).

Note that each auxiliary variable does not alter the total value for row j, i.e., the sum of 2i times ri+(j) and ri+(j) minus 2i times ri(j) and ri(j) across all i.

Thus, any solution to the new ILP must correspond to a solution of the original ILP. The converse is also true: the auxiliary variables can be adjusted to preserve the original value of the ILP. This is because any value for one of the rows of j can always be shifted to r0+(j) using the auxiliary variables, while still satisfying the constraints. Therefore, we can enforce the value of the unchanged variables.

2.5.2 From bounded to binary variables

Consider an ILP of the form

Ax =b
x u
x n

where A{Δ,,Δ}m×n. We will first transform this into an equivalent ILP of the form

Ax =b (8)
x {0,1}n

where A{Δ,,Δ}m×n for n(mΔ)O(m). Assume without loss of generality that each column of A is different. Otherwise, we can merge identical columns together by adding the respective upper and lower bounds. This implies that n(2Δ+1)m. Next, we compute a vertex solution x to the continuous relaxation {Ax=b,xu,xn}. The proximity bound by Eisenbrand and Weismantel [9] shows that there is an integer solution z with zx1m(2mΔ+1)m if any integer solution exists. Thus, choosing i=max{i,xi(2Δ+1)m} and ui=min{ui,xi+(2Δ+1)m} for i=1,2,,n, we can replace ,u by ,u without affecting feasibility. By shifting the solution, we can reduce the lower bound to zero and we arrive at the following ILP that is equivalent to the original one.

Ax =bA
xi {0,1,,uii} for all i=1,2,,n

Note that uii2m(2mΔ+1)m. Thus replacing each variable by uii binary variables we arrive at an ILP with n2m(2mΔ+1)mn2m(2mΔ+1)2m binary variables.

2.6 𝒏-Fold Integer Linear Programming

In this section, we prove Theorem 5. See 5 Consider the ILP

Ax =b (9)
x {0,1}n

with A{2m,,2m}m×n. We will show that this can be formulated as an equivalent n-Fold Integer Linear Program with parameter m and Δ=O(1). The reduction follows a similar idea as one in [10], which derives a lower bound based on Subset Sum. Note that if (9) had arbitrary variables (not necessarily binary) then we can use the reduction of the previous section to transform it into a binary one. For m3, define

B=(1001002121210){1,0,1,2}m×m.

This matrix has the property that the system Bx=(1,0,,0)𝖳,x0m has exactly two solutions, namely x=(0,,0,1) and x=(1,21,22,,2m2,0). Our n-Fold Integer Linear Program has one block Ai,Bi for each column Ai of A. Matrix Bi is defined as B above with right-hand side b(i)=(1,0,,0)𝖳. Matrix Ai is derived from Ai as follows: consider a coefficient Aji. We rewrite

Aji=λ020+λ121++λm22m2 with λ{2,,2}m1.

Such a λ exists since |Aji|2m. Then we set the jth row of Ai as (λ𝖳,0). Let x(i) be the variables corresponding to block Ai,Bi. By choice of Bi,b(i) there are exactly two settings of x(i) that satisfy Bix(i)=b(i), namely x(i)=(0,,0,1) and x(i)=(20,21,,2m2,0). Thus Aix(i){(0,,0)𝖳,Ai}. Hence, the n-Fold Integer Linear Program with b(0)=b is equivalent to (9).

3 Algorithm for few distinct variables

In this section, we prove Theorem 6.

See 6

We assume without loss of generality that in (1) we have =(0,0,,0). Note that otherwise, one may obtain an equivalent ILP with =(0,0,,0), u=u, and b=bA. We first decompose each ui into a sum of powers of two with the properties described in the following lemma. Such a construction is well-known in literature, see e.g. [18, 4, 16].

Lemma 18 (Cover).

For every integer k and hlogk, there exist integers c0(k),,ch(k){0,1,2} such that

{i=0h2ixi:0xici(k) for all 0ih}={0,1,,k}.

We call such a set c0(k),,ch(k) a cover of k. This set can be found in polynomial time in h.

Proof.

For n, let bini(n){0,1} denote the ith bit of the binary representation of n. Let B:=2h1 be the bottom bits, and let T=kB represent the top bits of k. Now, consider the sets

SB :={i=0h12ixi:0xibini(B) for all 0ih1} and
ST :={i=0h2ixi:0xibini(T) for all 0ih}.

We will set ci(k):=bini(B)+bini(T){0,1,2}. Showing that these numbers are a cover of k is equivalent to

SBST:={b+tbSB,tST}={0,1,,k}.

First, observe that SB={0,1,,2h1}. Moreover, there is no gap of length at least 2h in the set ST, that is, for every nonzero aST, there exists a smaller bST such that ab<2h. This b can be constructed by flipping an arbitrary bit of a to 0. Therefore, SBST consists of consecutive numbers. The smallest number in SBST is clearly 0, and the largest is B+T=k. We set h=log2(u). Using the lemma above, for each i, we decompose ui=c0(ui)20+c1(ui)21++ch(ui)2h with its cover. We can now naturally rewrite (1) as

maxi=0h 2ic𝖳z(i)
i=0h2iAz(i) =b
0zi(k) ck(ui) k{0,,h}
z(0),,z(h) n.

Each z(j) produces a partial solution for some unknown right-hand side b(j)=2jAz(j). We write b(j)=20Az(0)+21Az(1)++2jAz(j).

Our approach is now to compute, for j=0,1,,h and for every potential value of b(j), a solution z(0),z(1),,z(j). To do this, we first reduce the search space of relevant vectors b(j).

Lemma 19.

Consider Am×n and bm with AΔ. Suppose that y=y(0)20+y(1)21++y(h)2h satisfies Ay=b and 0y(j)u(j) with u(j){0,1,2}n for each j{0,,}. Then for b(j)=20Ay(0)+21Ay(1)++2jAy(j), we have

b(j)bmod2j+1

and furthermore

b(j){2j+2mnΔ,,2j+2mnΔ}m.
Proof.

The first property follows from the observation that b(>j):=bb(j) is a vector with each component being a multiple of 2j+1. Hence, b(j)bb(>j)bmod2j+1.

For the second property, observe that y(h)1u(h)12n for each h. Therefore, b(j)h=0j2h+1nΔ2j+2nmΔ. We say that a vector bm is relevant for j if bbmod2j+1 and b2j+2mnΔ. Clearly, the following holds:

Claim 20.

For every j, the number of relevant vectors for j is O(mnΔ)m.

We will now iteratively compute solutions for all vectors relevant for j+1 from the solutions for all relevant vectors for j with j0. Note that this will immediately establish Theorem 6.

Lemma 21.

Let 𝒮j be a set of optimal solutions to (1) for all bm that are relevant for j. Then, in time nm+1O(mΔ)m, we can compute a set 𝒮j+1 of optimal solutions for all b′′m relevant for j+1.

Proof.

Let V be the set of all vectors bm with bbmod2j+1 and b2j+2mnΔ.

We define an edge-weighted directed acyclic graph with vertices {s}V(0)V(1)V(n), where V(0),V(1),,V(n) are n+1 copies of V, and s is a distinguished source vertex.

If j0, there is an edge from s to every vertex vbV(0) such that the vector vb corresponds to a relevant vector bm for j for which (1) has a solution xb. This edge indicates feasibility, and the weight of the edge from s to vb is the value c𝖳xb for the optimal solution xb. In the base case where j<0, there is exactly one edge of weight 0 to the vertex in V(0) that corresponds to the all-zero vector.

For each vertex in V(i1) for 0<in, there is an edge to the corresponding vertex in V(i) with weight zero. Further, if cj+1(ui)1, for every vertex corresponding to b in V(i1), there is an edge to the vertex in V(i) that corresponds to b+2jAi (if it exists). The weight of this edge is 2jci.

Similarly, if cj+1(ui)2, then for every vertex in V(i1) that corresponds to a relevant b, there is an edge to a vertex in V(i) that corresponds to b+2j+1Ai (if it exists), with a cost of 2j+1ci.

Finally, we compute the longest path from s to each vertex in V(n), and we store these as the values of the solutions to all the relevant right-hand sides for j+1.

For the running time, observe that by 20, we have |V|O(mnΔ)m. Hence, the graph has nm+1O(mΔ)m vertices and edges. Thus, the longest path problem can be solved in time nm+1O(mΔ)m.

For correctness, consider a path in the graph from vertex vb1V(0) to vertex vb2V(n) (corresponding to vectors b1 and b2 respectively). The edges of this path define a vector z(j+1) such that 0z(j+1)cj+1(u). Moreover, by construction, it holds that 2jAz(j+1)+b1=b2. Finally, the weight of this path corresponds to the value 2jc𝖳z(j+1).

References

  • [1] Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for subset sum and bicriteria path. ACM Transactions on Algorithms (TALG), 18(1):1–22, 2022. doi:10.1145/3450524.
  • [2] Karl Bringmann. Fine-grained complexity theory. In Proceedings of STACS, page 1, 2019.
  • [3] Moses Charikar, Alantha Newman, and Aleksandar Nikolov. Tight Hardness Results for Minimizing Discrepancy. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 1607–1614. SIAM, 2011. doi:10.1137/1.9781611973082.124.
  • [4] Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results. In Proceedings of SODA, pages 4828–4848, 2024. doi:10.1137/1.9781611977912.171.
  • [5] Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschröder, Lars Rohwedder, and Robert Weismantel. Block-structured integer and linear programming in strongly polynomial and near linear time. In Proceedings of SODA, pages 1666–1681, 2021. doi:10.1137/1.9781611976465.101.
  • [6] Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Transactions on Algorithms (TALG), 12(3):1–24, 2016. doi:10.1145/2925416.
  • [7] Daniel Dadush, Arthur Léonard, Lars Rohwedder, and José Verschae. Optimizing low dimensional functions over the integers. In Proceedings of IPCO, pages 115–126, 2023. doi:10.1007/978-3-031-32726-1_9.
  • [8] Friedrich Eisenbrand, Lars Rohwedder, and Karol Węgrzycki. Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1610–1620, 2024. doi:10.1109/FOCS61266.2024.00100.
  • [9] Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Transactions on Algorithms (TALG), 16(1):1–14, 2019. doi:10.1145/3340322.
  • [10] Christoph Hunkenschröder, Kim-Manuel Klein, Martin Kouteckỳ, Alexandra Lassota, and Asaf Levin. Tight lower bounds for block-structured integer programs. In Proceedings of IPCO, pages 224–237, 2024. doi:10.1007/978-3-031-59835-7_17.
  • [11] Klaus Jansen and Lars Rohwedder. On integer programming, discrepancy, and convolution. Mathematics of Operations Research, 48(3):1481–1495, 2023. doi:10.1287/MOOR.2022.1308.
  • [12] Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of operations research, 12(3):415–440, 1987. doi:10.1287/MOOR.12.3.415.
  • [13] Dušan Knop, Martin Kouteckỳ, and Matthias Mnich. Combinatorial n-fold integer programming and applications. Mathematical Programming, 184(1):1–34, 2020. doi:10.1007/S10107-019-01402-2.
  • [14] Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight complexity lower bounds for integer linear programming with few constraints. ACM Transactions on Computation Theory (TOCT), 12(3):1–19, 2020. doi:10.1145/3397484.
  • [15] Hendrik W. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research, 8(4):538–548, 1983. doi:10.1287/MOOR.8.4.538.
  • [16] Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990.
  • [17] Christos H. Papadimitriou. On the complexity of integer programming. Journal of the ACM (JACM), 28(4):765–768, 1981. doi:10.1145/322276.322287.
  • [18] Adam Polak, Lars Rohwedder, and Karol Węgrzycki. Knapsack and subset sum with small items. In Proceedings of ICALP, pages 1–19, 2021. doi:10.4230/LIPICS.ICALP.2021.106.
  • [19] Victor Reis and Thomas Rothvoss. The subspace flatness conjecture and faster integer programming. In Proceedings of FOCS, pages 974–988, 2023. doi:10.1109/FOCS57990.2023.00060.
  • [20] Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Proceedings of IPEC, 2015. doi:10.4230/LIPIcs.IPEC.2015.17.