N-fold integer programming via LP rounding
share
We consider N-fold integer programming problems. After a decade of continuous progress, the currently fastest algorithm for N-fold integer programming by Jansen et al. (2019) has a running time of (rsΔ)^O(r^2s + s^2)ϕ^2 · nt log^O(1)(nt). Here ϕ is the largest binary encoding length of a number in the input. This algorithm, like its predecessors are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach that is not based on augmentation. Our algorithm relies on a stronger LP-relaxation of the N-fold integer program instead. This relaxation can be solved in polynomial time with parameter dependence (sΔ)^O(s^2) by resorting to standard techniques from convex optimization. We show that, for any given optimal vertex solution x^* of this relaxation, there exists an optimal integer solution z^* that is within short ℓ_1-distance, namely x^* - z^*_1≤ (rsΔ)^O(rs). With dynamic programming one can then find an optimal integer solution of the N-fold IP in time (rsΔ)^O(r^2s + s^2) nt. This, together with an off-the-shelf-method from convex optimization, results in the currently fastest algorithm for N-fold integer programming.
READ FULL TEXT