Fine-Grained Equivalence for Problems Related to Integer Linear Programming
Lars Rohwedder Karol Węgrzycki

Signature of maturity in cryptocurrency volatility
    Bikas K. Chakrabarti 
    September 9, 2024
==================================================

§ ABSTRACT 
Integer Linear Programming with n binary variables and m many 0/1-constraints can be solved in time 2^Õ(m^2)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 2^O(m^2-ε)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 n^O(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 n'^O(m) + O(nm), where n' is the number of distinct (i.e., non-symmetric) variables.
This dominates both of the aforementioned running times.





§ INTRODUCTION

The study of parameterized complexity for Integer Linear Programming has a long history:
classical works
by Lenstra <cit.> and Kannan <cit.> and very recently Rothvoss and Reis <cit.> provide FPT algorithms in the number of variables n of an ILP of the form
Ax ≤ b,  x∈ℤ^n.
In an orthogonal line of research,
Papadimitriou <cit.> gave an FPT algorithm in the number of constraints and the size of the coefficients of A and b for an ILP in standard form Ax = b,  x∈ℤ^n_≥ 0.
Interest in the second line of work has been renewed by the improved algorithms due to Eisenbrand, Weismantel <cit.> and Jansen, Rohwedder <cit.>, which give essentially optimal running times (mΔ)^O(m)(n) due to a conditional lower bound based
on the Exponential Time Hypothesis (ETH) <cit.>. 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 definition below.
Integer Linear Programming
	Constraint matrix A∈{-Δ,…,Δ}^m× n, right-hand side b∈ℤ^m, variable bounds ℓ, u∈ℤ_≥ 0^n.
	
		Find x∈ℤ^n with
		
    A x    = b 
    ℓ_i ≤    x_i ≤ u_i    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
	Constraint matrix A∈{-Δ,…,Δ}^m× n, right-hand side b∈ℤ^m.
	
        Find x∈{0,1}^n with
		
    A x    = b.

	
The running times obtained in <cit.> for either variant is (mΔ)^O(m^2)(n). Also for matrices with only 0/1 coefficients nothing better than 2^Õ(m^2)(n) is known.
It is an intriguing question whether the slightly unusual exponent of Õ(m^2) is necessary,
which is in the spirit of fine-grained complexity.
Since the dominant complexity-theoretic assumption of P≠NP 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.,  <cit.>.
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 Ω(mlog m) from the easier unbounded setting <cit.>,
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 are all equivalent with respect to improvements on their running time.

[ILP Hypothesis]
    For every > 0, there is no 2^O(m^2-)(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.
Many of them are well known applications of ILP techniques, see e.g. <cit.>.
Closest String with Binary Alphabet
	Alphabet Σ = {0, 1}, strings s_1,s_2,…,s_m∈Σ^n
	
		Find string t∈Σ^n minimizing
		
    max_i d(t, s_i) ,

		where d(t, s_i) is the Hamming distance between t and s_i, i.e., the number of positions the two strings differ in.
	
	We refer to the generalization with arbitrary Σ simply as Closest String.

Discrepancy Minimization
	Universe U = {1,2,…, n}, set system S_1,S_2,…,S_m⊆ U
	
		Find coloring χ : U →{-1, 1} minimizing
		
    max_i |∑_u∈ S_iχ(u)| .

	

Set Multi-Cover
	Universe U = {1,2,…,m}, set system S_1,S_2,…,S_n⊆ U, b∈ℕ
	
		Find I⊆{1,2,…,n} of minimal cardinality such that for each v∈ U
		there are at least b sets S_i with i∈ I.
	

Set Multi-Packing
	Universe U = {1,2,…,m}, set system S_1,S_2,…,S_n⊆ U, b∈ℕ
	
		Find I⊆{1,2,…,n} of maximal cardinality such that for each v∈ U
		there are at most b sets S_i with i∈ I.
	
	As mentioned above, our main result is the following equivalence.
	
        The following statements are equivalent:
        
            
  * There exists an 2^O(m^2-)(n) algorithm for Integer Linear Programming with Δ = O(1) when
                > 0. 
            
  * There exists an 2^O(m^2-)(n) algorithm for
                Binary Integer Linear Programming with A∈{0,
                1}^m× n and n≤ m^O(m)  with
                > 0.
			
  * There exists an 2^O(m^2-)(n) algorithm for
                Closest String with Binary Alphabet with >
                0.
			
  * There exists an 2^O(m^2-)(n) algorithm for
                Discrepancy Minimization with >
                0.
			
  * There exists an 2^O(m^2-)(n) algorithm for
                Set Multi-Cover with > 0.
			
  * There exists an 2^O(m^2-)(n) algorithm for
                Set Multi-Packing  with >
                0.
		
	
	Note that <ref> is the negation of <Ref>.
	All problems in <Ref> 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.

	<Ref> 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.
    [Strong ILP Hypothesis]
	    For every > 0 and δ≥ 0, there is no 2^O(m^δ + 2-)(n) time algorithm for Integer Linear Programming with Δ = 2^m^δ.
    
    Note that <ref> is a special case of <ref> for δ = 0.
	Another interesting regime is the complexity of Integer Linear Programming with Δ = 2^m,
	because of a connection to block-structure integer programming, which we elaborate on later.
	There, the state-of-the-art algorithm requires time m^O(m^3)(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.
	
		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 n'≤m'^O(m').
	
	This implies that if there is an algorithm with running time 2^O(m^1.5-)(n) for Integer Linear Programming with A ∈{0,1}^m× n, then there is a 2^O(m^3-')(n) time algorithm for Integer Linear Programming with Δ = 2^m.

	One might hope to improve the theorem to m' = O(m √(logΔ)), since then a 2^O(m^2-)(n) time algorithm for 0/1 matrices would imply a 2^O(m^3-')(n) time
	algorithm for Δ = 2^m. However, such a reduction would imply the strong result
	that under ETH is equivalent to <Ref>. This is because
under ETH the Subset Sum problem, i.e., the case when m = 1, cannot be
solved in Δ^o(1)(n) time  <cit.> and the hypothetical reduction would be able to encode
an instance of Subset Sum into an ILP with m = O(√(Δ)).
	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(m^2), but this reduction seems useless since the resulting
	parameter range requires (Δ') ·(n) time due to the ETH lower bound mentioned above.

    Assuming <ref>, 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
	Square matrices A_1,…,A_n,B_1,…,B_n∈{-Δ,…,Δ}^m× m, right-hand sides b^(0),…,b^(n)∈ℤ^m.
	
		Find x^(1),…,x^(n)∈ℤ_≥ 0^m with
		
    A_1 x^(1) + … + A_n x^(n)   = b^(0)
    
    			B_1 x^(1)   = b^(1)
    ⋮
    
    			B_n x^(n)   = b^(n)

	

    
        For every δ > 0, 
		there is no algorithm with running time 2^O(m^3-δ)(n)
        for n-Fold Integer Linear Programming when the maximum
        absolute entry is bounded by Δ = O(1), unless <ref> is false.
	
	This matches the best algorithms known for the problem, see <cit.> and references therein. The reduction follows the same idea as used in <cit.>,
	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.

	

 §.§ Tightness of more general problems

	There are a number of 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 <Ref>.
	However, for these, we do not know if they are all equivalent.

	The algorithm by Eisenbrand and Weismantel <cit.> also works for the
	optimization version of ILP, i.e.,
	
    max c x,  A x = b,  ℓ≤ x ≤ u,  x∈ℤ^n .

	This leads to the same running time of (mΔ)^O(m^2)(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 <cit.> have shown that one can find the minimizer of
	g(Ax),  x ∈{0, 1}^n in time (mΔ)^O(m^2)(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 b∈ℤ^m, Eisenbrand, Rohwedder, and Węgrzycki <cit.>
	gave an algorithm that finds a basis B of M such that A x_B = b in time
	O(mΔ)^O(m^2)(n), where
	x_B 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
	m^O(m^2)(n) for example by casting it as the previous matroid problem <cit.> or as a block structured ILP, see <cit.>.

	

 §.§ Algorithm for few distinct variables

	We show that the running time of 2^Õ(m^2)(n) for Integer Linear Programming with Δ = O(1),
	i.e., the subject of <Ref>, 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 Δ.
	
		Consider the integer programming problem
	
    max    c x 
    
    		A x    = b 
    ℓ_i ≤ x_i    ≤ u_i    i=1,…,n 
    
    		x    ∈ℤ^n  .

		Let Δ be an upper bound on the absolute value of entries of A.
		The problem (<ref>) can be solved in time
		
    n^m+1· O(mΔ)^m ·log(‖ u - ℓ‖_∞) .

	
	Using standard reductions, see e.g. <Ref>, 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 A∈{0,1}^m× n.
	Here, the running time above implies an n'^O(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 2^O(m) + O(nm) time, after which u_∞≤ n.
	Furthermore, without loss of generality, the rows of A are linearly independent, thus m≤ n'.
	Hence, the overall running time is
	
    2^O(m) + O(nm) + n'^m+1· O(m)^m ·log n    ≤n'^O(m)·log n + O(nm) 
       ≤n'^O(m) + O(nm).

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

  
*Binary ILP with A∈{0,1}^m× n and a constant number of 1s in each column.
	Here, the number of distinct columns is polynomial in m and the previous case implies a running time
	of m^O(m) + O(nm), meaning that <Ref> does not extend to this special case.

	

§ REDUCTIONS

	The basic idea of all reductions for <Ref> is that we transform one problem with parameter m
	into another problem
	with parameter m' = O(m ·log^O(1) m). Additionally the size of the instance may only increase from n to 2^O(m^2-δ)(n) for some δ > 0.
	The concrete reductions we prove can be seen in <Ref>.
	

	

 §.§ 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 i ≤ j we
	write s[i… j] for the substring from the ith to the jth character.
    
	    <Ref>, Statement <ref> implies Statement <ref>
    
    
	The following is an ILP model for Closest String with Binary Alphabet.
	
    ∑_i=1^n x_i ·1_{s_j[i] = 0} + (1 - x_i) ·1_{s_j[i] = 1}   ≤ d     for all  j∈{1,2,…,m}
    
    		x    ∈{0, 1}^n

	One may add slack variables to turn the inequalities into equalities.
    
    
        <Ref>, Statement <ref> implies Statement <ref>
    
    
    We want to transform the following ILP
    
    A x    = b 
    
    		x    ∈{0, 1}^n

    where A∈{0, 1}^m× n, into an equivalent instance of Closest String.
	We first rewrite (<ref>) into a more convenient form.
	
        One can in polynomial time construct a matrix C∈{-1,1}^(2m+2) × 2n and some c∈ℤ^2m+2 such that (<ref>) is feasible if and only if there
		is a solution to
		
    C x    ≤ c 
    
    			x    ∈{0, 1}^2n.

		Furthermore, every feasible x for (<ref>) has x_1 + ⋯ + x_2n = 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 (<ref>) corresponds to a “non-uniform” variant of
	    Closest String. It can be reformulated as: given strings s_1,…,s_2m+2∈{0,1}^2n and bounds d_1,…,d_2m+2∈ℤ, find a string t ∈{0,1}^2n such that for each j = 1,…,m we have d(t, s_j) ≤ d_j. This follows from the ILP model given in the proof of <Ref>.
	    Furthermore, we have the guarantee that any solution has exactly n ones.
	To transform this into a regular instance, we add two more strings r_1, r_2 and
	to each string s_j we add 4n more characters, which makes a total of 6n characters per string.
	The strings of this instance s'_1,…,s'_2m+2,r_1,r_2 are defined as
	

	
		r_1 = (     0, …, 0,     0, …, 0, 0, …, 0,     0,
		………… ,0     ), 

		r_2 = (     1, …, 1,     1, …, 1, 1, …, 1,     0,
		…………,0     ), 

		s_j' = (     s_j   _2n  chars,     1, …, 1_n  chars, 0, …, 0_n  chars,      1, …, 1,_2n - d_j  chars0, …, 0_d_j  chars     ).
	
	

Here, we assume without loss of generality that d_j∈{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.
	    
		    If there is a string t'∈{0,1}^6n with distance at most 2n to r_1, r_2, and
		    s'_j, j=1,2,…,2m+2, then there is also a string t∈{0, 1}^2n with
		    distance at most d_j to s_j, j=1,2,…,2m+2.
	    
	    
		    If there is a string t∈{0, 1}^2n with
		    distance at most d_j to s_j, j=1,2,…,2m+2, then there is also a string 
		    t'∈{0,1}^6n with distance at most 2n to r_1, r_2, and
		    s'_j, j=1,2,…,2m+2.
	    
	    From these claims, the lemma follows immediately.
    

	
    We add variables x̅_1,…,x̅_n
	and force a solution to take exactly n many ones
		
    A x    = b 
    
    		x_1 + ⋯ + x_n + 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
	
    A' x -  1x̅   ≤ b' 
    
    		-A' x +  1x̅   ≤ -b' 
    
    		x_1 + ⋯ + x_n + x̅_1 + ⋯ + x̅_n    ≤ n 
    
    		-x_1 - ⋯ - x_n - x̅_1 - ⋯ - x̅_n    ≤ - n 
    
            x,x̅   ∈{0, 1}^n

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

	
	Suppose there is a string t'∈{0,1}^6n with distance at most 2n to each of the strings s'_1,…,s'_2m+2,r_1,r_2.
    Because d(r_1,r_2) = 4n, string t' must match r_1 and r_2 on characters where r_1 and
    r_2 match. More precisely, 
        t'[i] = 0 for i ∈{4n,…,6n}.
    Formally, this follows because of
	
    4n    ≥ d(t', r_1) + d(t', r_2) 
       = d(t'[1… 4n], r_1[1… 4n]) + d(t'[1… 4n], r_2[1… 4n]) 
          + 2 d(t'[4n+1… 6n], (0,…,0)) 
       ≥ d(r_1[1… 4n], r_2[1… 4n]) + 2 d(t'[4n+1… 6n], (0,…,0)) 
       ≥ 4n + 2 d(t'[4n+1… 6n], (0,…,0)) .

        Let us now analyze the distance between t := t'[1… 2n] and s_j for some j.
        Since the last 2n characters of t' are zero, we have d(t'[4n+1… 6n], s'_j[4n+1… 6n]) = 2n - d_j. Thus,
        
    d(t, s_j)    ≤ d(t', s'_j) - d(t'[4n+1… 6n], s'_j[4n+1… 6n]) 
       ≤ 2n - (2n - d_j) = d_j .

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

	
		Let t ∈{0, 1}^2n with d(t[1… 2n], s_j) ≤ d_j for all j.
		We extend it to a string t'∈{0,1}^6n by setting t'[1… 2n] = t,
		t[2n+1… 3n] = (1,…,1), and
	t[3n+1… 6n] = (0,…,0).
	Let us now verify that t' has a distance at most 2n to each string.
	For r_1, r_2 note that t[1… 2n] has exactly n ones by guarantee of the
	non-uniform instance. Thus, the distance to r_1 and r_2 is exactly 2n.
	Consider some j∈{1,…,2m+2}. Then
	
    d(s'_j, t) = d(s_j, t[1… 2n]) + 2n - d_j ≤ 2n .

    

	

 §.§ Discrepancy Minimization

	
    
        <Ref>, Statement <ref> implies Statement <ref>
    
    
	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
	
    [  A; -A ] y 
    			   ≤[ d; d; ⋮; d ]
    
    		y    ∈{-1, 1}^n.

	This can be equivalently formulated as
	
    [  2A; -2A ] x
    			   ≤[  A; -A ][ 1; 1; ⋮; 1 ] + [ 2d; 2d;  ⋮; 2d ]
    
    			x    ∈{0, 1}^n.

	where x_i = (1 + y_i) / 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.
    
    
        <Ref>, Statement <ref> implies Statement <ref>.
    
    
        Consider an ILP of the form
	
    A x    = b 
    
    		x    ∈{0, 1}^n

	for A∈{0, 1}^m× n and n≤ m^O(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
	
    A y    = b' 
    
    		y    ∈{-1, 1}^n

	where b' = 2b - A  (1,…,1).
	Note that x is feasible for (<ref>) if and only if y = 2x - (1, …, 1) is feasible for (<ref>). Also, if b' = (0, …, 0), then (<ref>) 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.
	
	For any k∈ℕ we can construct a pair of matrices B, B̅∈{0, 1}^(2k-1) × 2^k such that there are exactly two solutions to
	
    B z + B̅z̅   = [ 0; ⋮; 0 ]
     
    			z,z̅   ∈{-1, 1}^2^k

	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 = ⌈log_2 n ⌉ = O(mlog m) we now
    replace each coefficient b'_j in the previous system by the variables from the gadget.
	Note that (<ref>) is infeasible if b' _∞ > n.
    Thus assume without loss of generality that b' _∞≤ n ≤
    2^k.
	Let C, C̅∈{0, 1}^2^k × m be defined as follows.
	The jth row of C has b'_j many ones at arbitrary positions if b'_j ≥ 0 and is all zero otherwise; contrary, the jth row of C̅ has -b'_j many ones at arbitrary positions if b'_j < 0 and is all zero otherwise.

	Now consider the system
	
    A y + C z + C̅z̅   = [ 0; ⋮; 0 ]
    
    			B z + B̅z̅   = [ 0; ⋮; 0 ]
     
    			y    ∈{-1, 1}^n 
    
    			z,z̅   ∈{-1, 1}^2^k.

	We claim that (<ref>) has a solution if and only if there is a solution to (<ref>). Let y, z, z̅ be a solution to the former. Notice that the negation of a solution is also feasible.
	Due to <ref> we may assume without loss of generality that z = (-1,…,-1) and z̅ = (1, …, 1), negating the solution if necessary.
	It follows that
	
    C z + C̅z̅ = -b' .

	Thus, Ay = b', which concludes the first direction.
	For the other direction, assume that there is a solution y to (<ref>).
	We set z = (-1,…,-1), z̅ = (1,…,1), which by <Ref>
	satisfies B z + B̅z̅ = (0, …, 0). As before we have that C z + C̅z̅ = -b'. Thus, y, z, z̅ is a solution to (<ref>).
	This establishes the equivalence of the initial ILP instance to (<ref>),
	which corresponds to an instance of Discrepancy Minimization where we test for discrepancy
	zero with m' = O(mlog m) sets.
    

	
	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}^(2k-1) × 2^k as above.
    Then we set
	
    B' = [     B     0; 1 ⋯ 1 0 ⋯ 0; 0 ⋯ 0 1 ⋯ 1 ] and B̅' = [    B̅     0; 0 ⋯ 0 1 ⋯ 1; 1 ⋯ 1 0 ⋯ 0 ]∈{0,1}^(2k+1) × 2 · 2^k
    		.

		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' [  z; z' ] + B̅' [  z̅; z̅' ] = [ 0; ⋮; 0 ] .

		Now take any z,z',z̅, z̅'∈{-1,1}^2^k+1 that satisfy (<ref>).
		Then we have that B z + 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
		
    2^k + ∑_i=1^2^kz̅'_i = ∑_i=1^2^k z_i + 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̅.
	
	
	
	

 §.§ Set Multi-Cover

	
    
        <Ref>, Statement <ref> implies Statement <ref>.
    
    
        
    
    
	An instance of the decision version of Set Multi-Cover with a bound
    d on the cardinality can be formulated as
	
    x_1 + ⋯ + x_n    ≤ d 
    
    		A x    ≥[ b; ⋮; b ]
    
    		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 (<ref>) 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.
    
        <Ref>, Statement <ref> implies Statement <ref>.
    
    
        
    
    

    First, we reduce to
	a “non-uniform” version of Set Multi-Cover where each element v has a different
	demand b_v.
	Let A∈{0,1}^m× n and b∈ℤ_≥ 0^m 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 
    
    		x_1 + ⋯ + x_n + x̅_1 + ⋯ + x̅_n    = n 
    
    		x    ∈{0, 1}^n 
    x̅   ∈{0, 1}^n.

	This system is equivalent to the previous one, by setting n - x_1 - ⋯ - x_n arbitrary variables x̅_i to 1. Next, we transform the equality constraints Ax = b into inequalities:
	
    Ax    ≥ b 
    
    		( 1 - A) x +  1x̅   ≥[ n; ⋮; n ] - b 
    
    		x_1 + ⋯ + x_n + x̅_1 + ⋯ + x̅_n    = n 
    
    		x    ∈{0, 1}^n 
    
    		y    ∈{0, 1}^n.

	Here, 1 denotes the n× n all-ones matrix.
	Note that the second constraint is equivalent to Ax ≤ b, 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    x_1 + ⋯ + x_n + x̅_1 + ⋯ + x̅_n 
    
    		Ax    ≥ b 
    
    		( 1 - A) x +  1x̅   ≥[ n; ⋮; n ] - b 
    
    		x_1 + ⋯ + x_n + 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 S_1,…,S_n, (b_v)_v∈ U, 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 n - b_v many arbitrary new sets.
    

	

 §.§ Set Multi-Packing

	
    
        <Ref>, Statements <ref> and <ref> are equivalent.
    
    
	Notice the following duality between Set Multi-Cover and Set Multi-Packing.
	Let U = {1,2,…,m}, S_1,S_2,…,S_n, and b∈ℕ be an instance of Set Multi-Cover. Now consider the instance of Set Multi-Packing with universe U, set system S̅_1 = U∖ S_1, S̅_2 = U∖ S_2, …, S̅_n = U∖ S_n, and bounds b̅ = n - b. 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 n - k.
    

	

 §.§ Integer Linear Programming

	

    In this section, we prove <Ref>, i.e., we show how to
    reduce an ILP with large coefficients into a (larger) ILP with only 0/1
    coefficients.  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 <ref>
    and <ref> are equivalent and concludes the proof
    of <ref>.

	

  §.§.§ 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 = ⌈log_2(Δ) ⌉.
	For the jth row of A we introduce 4 (k + 1) 
	rows in A', denoted by r^+_0(j), r'^+_0(j), …, r^+_k(j), r'^+_k(j), r^-_0(j), r'^-_0(j), …, r^-_k(j), r'^-_k(j).
	Intuitively, the rows r^+_i(j), r'^+_i(j) are symmetric rows that each stand for a value of 2^i in row j. Similarly, r^-_i(j), r'^-_i(j) stand for a value of -2^i in row j.
	The right-hand sides of the new ILP are b_j for row r^+_0(j) and zero for all other rows affiliated with j.

	For each column A_i we derive a column of A' as follows: for row j
	we consider the binary encoding of A_ji and have the column in A' use this
	binary encoding in r^+_0(j), r^+_1(j), r^+_k(j) if A_ji≥ 0 and in
	r^-_0(j), r^-_1(j), r^-_k(j) if A_ji < 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,…,k-1 we add:
	
		
  * a variable with a one in row r^+_i(j), r'^+_i(j) and r^-_i+1(j) and
		
  * a variable with a one in row r^-_i(j), r'^-_i(j) and r^+_i+1(j).
	
	Furthermore, for each row j and each i = 0,…,k we add:
	0pt
		
  * a variable with a one in row r'^+_i(j) and r^-_i(j),
		
  * a variable with a one in row r'^-_i(j) and r^+_i(j), and
		
  * a variable with a one in row r^-_i(j) and r^+_i(j).
	
	Note that each auxiliary variable does not change the total value for row j,
	i.e., the sum of 2^i times rows r^+_i(j) and r'^+_i(j) minus 2^i times r^-_i(j) and r'^-_i(j) over all i.
	Thus, any solution to the new ILP must form a solution to the original ILP.
	The converse is also true, since any value for one of the rows of j can always be shifted to r^+_0(j) via the auxiliary variables.

	

  §.§.§ 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
	
    A'x    = b' 
    
    		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, ℓ≤ x ≤ u, x∈ℝ^n}.
	The proximity bound by Eisenbrand and Weismantel <cit.> shows that there is an integer solution z with
	z - x^*_1 ≤ m (2mΔ+1)^m if any integer solution exists.
	Thus, choosing ℓ'_i = max{ℓ_i, ⌈ x^*_i ⌉ - (2Δ+1)^m}
	and u'_i = min{u_i, ⌊ x^*_i ⌋ + (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    = b - Aℓ' 
    
    		x_i    ∈{0,1,…, u'_i - ℓ'_i}    for all  i=1,2,…,n

	Note that u'_i - ℓ'_i ≤ 2m (2mΔ+1)^m. Thus replacing each variable by u'_i - ℓ'_i binary variables we arrive at an ILP with n' ≤ 2m (2mΔ+1)^m · n ≤ 2m (2mΔ+1)^2m binary variables. 

	

 §.§ n-Fold Integer Linear Programming

	
    In this section, we prove <ref>. Consider the ILP
	
    Ax    = b 
    
    		x    ∈{0, 1}^n

	with A∈{-2^m,…,2^m}^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 <cit.>,
	which derives a lower bound based on Subset Sum.
	Note that if (<ref>) had arbitrary variables (not necessarily binary)
	then we can use the reduction of the previous section to transform it into a binary one.
    For m ≥ 3, define
	
    B = [  1  0     ⋯  0  1;  0        ⋯     0;  2 -1     ⋯      ;     2 -1  ⋯     ⋮;           ⋱      ;           2 -1  0 ]∈{-1,0,1,2}^m× m.

	This matrix has the property that the system Bx = (1,0,…,0), x∈ℤ_≥ 0^m has exactly two solutions, namely x = (0,…,0,1) and x = (1,2^1,2^2,…,2^m-2,0).
	Our n-Fold Integer Linear Program has one block A'_i, B'_i for each column A_i of A.
	Matrix B'_i is defined as B above with right-hand side b'^(i) = (1,0,…,0).
	Matrix A'_i is derived from A_i as follows: consider a coefficient A_ji.
	We rewrite
	
    A_ji = λ_0 · 2^0 + λ_1 · 2^1 + ⋯ + λ_m-2· 2^m-2 with λ∈{-2,…,2}^m-1 .

	Such a λ exists since |A_ji| ≤ 2^m.
	Then we set the jth row of A'_i as (λ, 0). Let x^(i) be the variables corresponding to block A'_i, B'_i. By choice of B'_i, b'^(i) there are exactly two settings of x^(i) that satisfy B'_i x^(i) = b'^(i), namely x^(i) = (0,…,0,1) and x^(i) = (2^0,2^1,…,2^m-2,0). Thus
	A'_i x^(i)∈{(0,…,0), A_i}.
	Hence, the n-Fold Integer Linear Program with b^(0) = b is equivalent to (<ref>).



§ ALGORITHM FOR FEW DISTINCT VARIABLES
 
In this section, we prove <ref>. We assume without loss of generality that in (<ref>)
we have ℓ = (0, 0,…, 0). Note that otherwise, one may obtain an equivalent ILP with
ℓ = (0, 0,…, 0), u' = u - ℓ, and b' = b - Aℓ.
We first decompose each u_i 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. <cit.>.

    For every integer k ∈ℕ and h ≥⌊logk⌋,
    there exist integers c_0(k),…,c_h(k) ∈{0,1,2} such that
    
        { ∑_i=0^h 2^i x_i : 0 ≤x_i ≤c_i(k)  for
            all  0 ≤i ≤h
        } = {0,1,…,k}
        .
    
    We call such a set c_0(k),…,c_h(k) a cover of k. This set
    can be found in polynomial time in h.


    For n ∈ℕ, let _i(n) ∈{0,1} denote the ith bit of the binary
    representation of n. Let B := 2^h - 1 be the bottom bits, and let T
    = k - B represent the top bits of k.
    Now, consider the sets
    
    S_B    := {∑_i=0^h-1 2^i x_i : 0≤ x_i ≤_i(B)  for all  0≤ i ≤ h-1 } and
    
    	    S_T    :=
            {∑_i=0^h 2^i x_i : 0≤ x_i ≤_i(T)  for all  0≤ i ≤ h }.

    We will set c_i(k) := _i(B) + _i(T) ∈{0,1,2}. Showing that these numbers are a cover of k is equivalent to
    
        S_B ⊕S_T := { b + t |b ∈S_B, t ∈S_T} = {0,1,…,k}.
    
    First, observe that S_B = {0,1,…,2^h - 1}. Moreover, there is
    no gap of length at least 2^h in the set S_T, that is, for every nonzero a ∈ S_T,
    there exists a smaller b ∈ S_T such that a-b < 2^h. This b can be
    constructed by flipping an arbitrary bit of a to 0. Therefore, S_B ⊕ S_T consists of
    consecutive numbers. The smallest number in S_B ⊕ S_T is clearly 0,
    and the largest is B+T = k.
    
We set h = ⌊log_2(‖ u ‖_∞) ⌋. Using the lemma above, for each i, we decompose
u_i = c_0(u_i) · 2^0 + c_1(u_i) · 2^1 + ⋯ + c_h(u_i) · 2^h with its cover.
We can now naturally rewrite (<ref>) as

    max∑_i=0^h    2^i c z^(i)
    ∑_i=0^h 2^i Az^(i)   = b
    
    	0 ≤ z^(k)_i    ≤ c_k(u_i)    k ∈{0,…,h}
    
        z^(0),…,z^(h)   ∈ℤ^n  .

Each z^(j) produces a partial solution for some unknown right-hand side
b^(j) = 2^j A z^(j). We write b^(≤ j) = 2^0 Az^(0) + 2^1 Az^(1) + ⋯ + 2^j Az^(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).


    Consider A ∈ℤ^m× n and b ∈ℤ^m with
    A_∞≤Δ.
    Suppose that y = y^(0)· 2^0 + y^(1)· 2^1 + ⋯ +
    y^(h)· 2^h satisfies A y = b and 0 ≤ y^(j)≤ u^(j)
    with u^(j)∈{0,1,2}^n for each j ∈{0,…,ℓ}. Then for b^(≤ j) = 2^0 Ay^(0) + 2^1 Ay^(1) + ⋯ + 2^j Ay^(j), we have
    
    b^(≤ j)≡ b  2^j+1

    and furthermore
    
    b^(≤ j)∈{- 2^j+2 mnΔ, …, 2^j+2 mnΔ}^m  .



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

    For the second property, observe that ‖ y^(h)‖_1 ≤‖
    u^(h)‖_1 ≤ 2n for each h. Therefore,
    ‖ b^(≤ j)‖_∞≤∑_h=0^j 2^h+1nΔ≤ 2^j+2 nmΔ.

We say that a vector b' ∈ℤ^m is relevant for j if b' ≡ b  2^j+1 and ‖ b' ‖_∞≤ 2^j+2 mnΔ.
Clearly, the following holds:



    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 j ≥ 0.
Note that this will immediately establish <ref>.


    Let 𝒮_j be a set of optimal solutions to (<ref>) for all
    b' ∈ℤ^m that are relevant for j. Then, in time n^m+1·
    O(mΔ)^m, we can compute a set 𝒮_j+1 of optimal solutions for all b”∈ℤ^m relevant for j+1.



Let V be the set of all vectors b' ∈ℤ^m with b'
≡ b  2^j+1 and ‖ b' ‖_∞≤ 2^j+2 mnΔ.

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 j ≥ 0, there is an edge from s to every vertex v_b'∈ V^(0) such that
	the vector v_b' corresponds to a relevant vector b' ∈ℤ^m for j for which (<ref>) has a solution x_b'. This edge indicates feasibility, and the weight of the edge from s to v_b' is the value c x_b' for the optimal solution x_b'.
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^(i-1) for 0 < i ≤ n, there is an edge to the corresponding vertex in V^(i) with weight zero. Further, if 
c_j+1(u_i) ≥ 1, for every vertex corresponding to b' in V^(i-1),
there is an edge to the vertex in V^(i) that corresponds to b' + 2^j A_i
(if it exists). The weight of this edge is 2^j c_i. 

Similarly, if c_j+1(u_i) ≥ 2, then for every vertex in V^(i-1)
that corresponds to a relevant b', there is an edge to a vertex in V^(i)
that corresponds to b' + 2^j+1 A_i (if it exists), with a cost of 2^j+1c_i.

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 <ref>, we have |V| ≤
O(mnΔ)^m. Hence, the graph has n^m+1· O(mΔ)^m vertices
and edges. Thus, the longest path problem can be solved in time n^m+1· O(mΔ)^m. 

For correctness, consider a path in the graph from vertex v_b_1∈
V^(0) to vertex v_b_2∈ V^(n) (corresponding to vectors b_1 and b_2
respectively). The edges of this path define a vector z^(j+1) such that 0 ≤
z^(j+1)≤ c_j+1(u). Moreover, by construction, it holds that 2^j A
z^(j+1) + b_1 = b_2. Finally, the weight of this path corresponds to the value
2^j c z^(j+1).




plain

