Answers are grounded in this paper and cite their sources.
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^x + g(Ax), where c is a rational cost vector, A is an integral matrix with d rows, and g Zᵈ → Q∪ \+∞\ is an arbitrary function. We access g via an oracle that minimizes c^x + g(Ax) when all but $O(d)$ variables are fixed. Our algorithm runs in time (ndΔ)O(d)(Q + 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Δ)O(d²)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)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ₘₐₓO(d)poly(|I|) where wₘₐₓ is the maximum weight of an item and d the number of different weights.
No takes yet. Share an insight, caveat, or question.
Jansen et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: