Delta-modular ILP Problems of Bounded Co-dimension, Discrepancy, and Convolution

Abstract

For k,n≥0, and c∈Zn, we consider ILP problems max{c⊤x:Ax=b,x∈Zn≥0} with A∈Zk×n, rank(A)=k, b∈Zk andmax{c⊤x:Ax≤b,x∈Zn} with A∈Z(n+k)×n, rank(A)=n, b∈Zn+k. The first problem is called an \emph{ILP problem in the standard form of the codimension k}, and the second problem is called an \emph{ILP problem in the canonical form with n+k constraints.} We show that, for any sufficiently large Δ, both problems can be solved with 2O(k)⋅(fk,d⋅Δ)2/2Ω(log(fk,d⋅Δ)√) operations, where fk,d=min{kk/2,(logk⋅log(d+k))k/2}, d is the dimension of a corresponding polyhedron and Δ is the maximum absolute value of rank(A)×rank(A) sub-determinants of A. As our second main result, we show that the feasibility variants of both problems can be solved with 2O(k)⋅fk,d⋅Δ⋅log3(fk,d⋅Δ) operations. The constant fk,d can be replaced by other constant gk,Δ=(logk⋅log(kΔ))k/2 that depends only on k and Δ. Additionally, we consider different partial cases with k=0 and k=1, which have interesting applications. As a result of independent interest, we propose an n2/2Ω(logn√)-time algorithm for the tropical convolution problem on sequences, indexed by elements of a finite Abelian group of the order n. Additionally, we give a complete, self-contained error analysis of the generalized Discrete Fourier Transform for Abelian groups with respect to the Word-RAM computational model.