CS Paper Radar

Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

Klaus Jansen, Felix Ohnesorge, Björn Schumacher

cs.DS ·submitted 2026-11-12 13:55 UTC · v1

Abstract

We consider a special block-structured integer program with $n$ blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective $c^{\intercal}x + g(Ax)$, where $c$ is a rational cost vector, $A$ is an integral matrix with $d$ rows, and $g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\}$ is an arbitrary function. We access $g$ via an oracle that minimizes $c^{\intercal}x + g(Ax)$ when all but $O(d)$ variables are fixed. Our algorithm runs in time $(ndΔ)^{O(d)}(Q + \text{poly}(|I|))$ where $Δ$ is the largest absolute value of an entry in $A$, $Q$ is the necessary time to evaluate the oracle for $g$ and $|I|$ is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time $t^d(dΔ)^{O(d^2)}Q$ where $t$ is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time $(mΔ)^{O(m)}\text{poly}(|I|)$, where $m$ is the number of constraints involving integral variables and $Δ$ is the largest absolute value of coefficients of integral variables. This improves the dependence on $m$ in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time $w_{\max}^{O(d)}\text{poly}(|I|)$ where $w_{\max}$ is the maximum weight of an item and $d$ the number of different weights.

Closest papers

Nearest neighbours by meaning across the whole index.

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.71
Abstract

We generalize integer programming to the setting in which the image $A \mathbf{x}$ is restricted to an explicitly given rational polyhedron $P$. That is, we solve $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}\in P, \mathbf{x}\in\mathbb{Z}_{\geq 0}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and $P$ is an explicitly given rational polyhedron. We present a randomized algorithm running in time $(dΔ)^{O(d)}\operatorname{poly}(L)$ in this regime, where $Δ:= \|A\|_\infty$ and $L$ is the binary input length. This running time matches that of the best-known parameterized algorithms for integer programming, due to Eisenbrand and Weismantel and to Jansen and Rohwedder, and improves on the $O(d^2)$ exponent achieved by Dadush, Léonard, Rohwedder, and Verschae in a more general setting. This result enables several applications, including exact algorithms for integer programming and unbounded knapsack in which the consumed resources $A\mathbf{x}$ must satisfy arbitrary additional linear constraints. We also obtain a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant, resolving an open problem of Randolph and Węgrzycki. For integer programs with $m$ constraints and bounded row doubling, we obtain an $f(C,m)n^{O(m)}\operatorname{poly}(L)$-time algorithm and show that the dependence on $m$ in the exponent of $n$ is necessary under $\mathsf{W[1]}\ne\mathsf{FPT}$.

0.24

A Constructive FPT Algorithm for Integer Cone Optimization with Convex Costs

cs.DS ·2026-09-25 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.69
Abstract

We give a deterministic fixed-parameter algorithm for integer cone optimization with convex costs. Given $τ$ rational polytopes in $\R^{d+k}$, we combine generators whose first $d$ coordinates are integral and whose remaining $k$ coordinates may be fractional. Each generator has a convex cost depending only on its integer coordinates. We minimize the total cost of nonnegative integer combinations subject to arbitrary rational linear constraints on the full typewise aggregates and generator counts. Our algorithm runs in time \[ 2^{τ\log(τ+1)\,2^{O(d)}}\cdot |I|^{O(1)}, \] where $|I|$ is the total binary input length. It constructs an optimal representation using at most $2^{2d+1}$ distinct generators per type. The number $k$ of continuous coordinates contributes only to the polynomial input factor. For a single generator type, the running time becomes $2^{2^{O(d)}}\cdot |I|^{O(1)}$. Applications include constructive FPT algorithms for Cone and Polytope Intersection, high-multiplicity bin packing, vector bin packing, and makespan minimization on uniform and unrelated machines. The double-exponential dependence on $d$ is tight for Point-in-Cone and both bin-packing problems assuming $\mathrm{NP}\nsubseteq\mathrm{SUBEXP}$. The mixed-integer formulation also yields additive EPTASs for makespan minimization, machine covering, and envy minimization on identical machines, and additive schemes fixed-parameter tractable in $1/\varepsilon+τ$ on uniform machines.

0.24

Bounded Integer Programming in Almost $N^{2d}$ Time

cs.DS ·2026-10-19 ·Lin Chen, Yuchen Mao, Guochuan Zhang
theory similarity 0.67
Abstract

We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where $A\in\mathbb{Z}^{d\times n}$, all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers, and every variable bound is finite. Let $N$ be an upper bound on the absolute values of the entries of $A$, and $c_{\max}$ one on the absolute values of the costs. For every fixed $d$ and every fixed $\varepsilon>0$ we give a deterministic algorithm running in time \[ T_{\textrm LP}+O_d(n)+O_{d,\varepsilon}\bigl(N^{2d+\varepsilon}\log^2(c_{\max}+2)\bigr), \] where $T_{\textrm LP}$ is the time to solve one linear programming relaxation exactly. Prior to our work, the best known running time for bounded variables was $N^{O(d^2)}$ [Eisenbrand \& Weismantel'20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively, with the exponent $2d+\varepsilon$.

0.16

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.65
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.09

Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime

cs.DS cs.CC ·2026-10-18 ·Jadwiga Czyżewska, Karolina Drabik, Marek Sokołowski, Karol Węgrzycki
theory similarity 0.63
Abstract

The class $\mathsf{PPP}$ captures fundamental total search problems, for which a solution is guaranteed to exist by the pigeonhole principle and the main challenge is to find it. We ask whether problems in this class admit significantly faster algorithms in the \emph{dense regime}. More concretly, we study \emph{binary collision Short Integer Solution} (SIS): given a matrix $A\in\mathbb{Z}_q^{n\times m}$ with $m>n\log q$, the goal is to find distinct $\underline{\mathbf{x}},\underline{\mathbf{y}}\in\{0,1\}^m$ with $A\underline{\mathbf{x}}=A\underline{\mathbf{y}}\pmod q$. Brute-force enumeration can be used to find a collision in $q^{\mathcal{O}(n)} \operatorname{poly}(|I|)$ time, and no significantly faster algorithm for that problem is known. We present an algorithm running in time $q^{o(n)}\cdot\operatorname{poly}(|I|)$ whenever the density parameter $δ:= m/(n\log q)$ is $ω(1)$.\footnote{All logarithms are in base $2$, and $|I|$ is the binary input length.} Building on reductions of Sotiraki et al.~(FOCS~2018), we obtain corresponding algorithms for dense variants of weak constrained SIS, Equal Vector Sums, Minkowski, and Blichfeldt. Our algorithm adapts techniques of Bhati et al.~(FOCS~2026), who gave a subexponential algorithm for Equal Sums in the dense regime and proved a tight conditional lower bound. Their conditional lower bound easily transfers to SIS and shows that the running time of our algorithms is essentially optimal.

0.11

Vector Balancing in Polynomial Time

cs.DS math.CO ·2026-09-20 ·Shengtao Guo, Ethan X. Fang, Junwei Lu
hot directionhighly cited similarity 0.62
Abstract · 23 pages, no figures

The Komlós problem asks for signs $\varepsilon\in\{-1,1\}^n$ with $\|A\varepsilon\|_\infty$ bounded by an absolute constant whenever the columns of $A\in\mathbb R^{m\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic $O(\sqrt t)$-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most $t$ sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.

0.57

A Fixed-Parameter Algorithm for 4-Block Integer Programming

cs.CC cs.DS ·2026-09-20 ·Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz
similarity 0.62
Abstract

We give a fixed-parameter tractable (FPT) algorithm with running time $f(k,\barΔ)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute entry $\barΔ$ in the local-column blocks. This result resolves a long-standing open question in parameterized complexity, and answers a conjecture by Eisenbrand and Rothvoss (2026) in the positive. This result has several implications for other block-structured integer programming models, including mixed fracture number and special cases of 4-block programs with large entries outside of the diagonal. Important tools for this algorithm are structural properties of generalized $n$-fold integer programs shown by Ligthart~(2026) and an algorithm by Veselov, Gribanov, Zolotykh and Chirkov~(2020) for optimizing discrete convic functions. Independently and shortly after the first version of our paper appeared, Koutecký, Lassota, and Ligthart (2026) obtained an FPT algorithm for 4-block integer programming.

0.41

Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time

cs.DS ·2026-10-09 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.61
Abstract

We give an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for multidimensional subset sum on an explicitly listed multiset of $n$ vectors in $[-N,N]^d$, for every fixed $d$ and $\varepsilon>0$. This directly implies an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for feasibility test of integer programming. Prior to our work, the best-known algorithm has a running time of $O_{d}(n+N^{O(d^2)})$ [Eisenbrand, Weismantel'19]. Specifically, if $d=1$, our algorithm runs in $O_{\varepsilon}(n+N^{1+\varepsilon})$-time for the standard subset sum problem, which is near-linear in the largest input integer. Prior to our work, subset sum can be solved in time near-linear in the target $t$ [Bringmann'17], or near-linear in the mixed parameter $\sqrt{Nt}$ [Chen, Lian, Mao, Zhang'24]. It is a fundamental open problem whether the algorithm can be made near-linear in $N$, which is settled affirmatively in this paper up to an arbitrary small $N^{\varepsilon}$ term.

0.26