Pith. sign in

REVIEW 3 major objections 4 minor 60 references

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For separable convex integer programs with bounded coefficients and small primal treedepth, the paper gives an algorithm matching the information-theoretic lower bound of n log||u-l||_∞; for small dual treedepth it gives an algorithm…

desk verdict Strong, important algorithms for separable convex IP with small treedepth; two repairable proof bugs in the sensitivity lemma currently undercut the dual algorithm's correctness as written. read the letter →

arxiv 2505.22212 v1 pith:LADT3RGX submitted 2025-05-28 cs.DS math.OC

Christoph Hunkenschröder , Martin Koutecký , Asaf Levin , Tung Anh Vu This is my paper
classification cs.DSmath.OC MSC 90C1068Q2568W4090C25
keywords separableconvexintegerprogrammingtreedepthblock-structuredmatricesn-foldscalingalgorithmsGraverbasisconvolutiontreenear-lineartime
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that separable convex integer programs can be solved almost as fast as their information-theoretic limit allows, provided the constraint matrix is block-structured with small coefficients and small primal or dual treedepth. The lower bound of n log||u-l||_∞ comparisons is met by a scaling algorithm whose primal version runs in g(td_P, ||A||_∞) n log(max(||u-l||_∞, ||b||_∞)) time, while the dual (tree-fold) version runs in g(td_D, ||A||_∞) n log n log(max(||u-l||_∞, ||b||_∞)) time, only a log n factor slower. The payoff is that a large class of nonlinear integer programs inherit near-linear algorithms that were previously available mainly for linear objectives. The argument turns on a new sensitivity theorem: refining the scaling lattice one coordinate at a time moves the optimum by a bounded, sparse amount, so a dynamic convolution tree can apply the updates in logarithmic time.

What carries the argument

The machinery is a scaling loop combined with a new sensitivity bound and a new dynamic data structure. The scaling loop runs the problem on successively finer lattices 2^i Z^n, halving i each phase; in the dual algorithm each phase refines one coordinate at a time. Theorem 6 guarantees that when the set of refined coordinates changes from I to J, some optimum of the J-scaled instance lies within ℓ1-distance 2|I△J|g1(Ã) of the previous optimum, so each refinement is a sparse update. The convolution tree is a balanced binary tree over blocks of columns whose nodes store min-plus convolutions of partial solutions; it maintains the optimal solution of an ℓ1-bounded IP subproblem so that changing one coordinate's objective and bounds costs O(σ log n) time (with a parameter-dependent factor), and queries are independent of n.

What would settle it

Construct a single-row instance with a large negative optimal value and follow the encoding of Lemma 4: take x_i = -3, compute the aux-I-IP variables, decode them back, and check whether the decoded integer equals -3. If the round-trip fails on any negative input, the claimed bijection breaks and Theorem 6, along with the dual algorithm's correctness proof, loses its stated support.

Watch

Extended reading notes

Core claim

The central claim is that IP with a separable convex objective and a comparison oracle is fixed-parameter near-linear-time tractable when the constraint matrix has small coefficients and small primal or dual treedepth. Theorem 1 matches the n log||u-l||_∞ lower bound up to parameter dependence using a scaling loop fed by a strong proximity bound; Theorem 2 solves the dual treedepth case within a log n factor by refining the scaling lattice one variable at a time, guided by a new sensitivity bound (Theorem 6) and maintained by a convolution tree data structure. If correct, these results close most of the gap between upper and lower bounds for nonlinear objectives in the block-structured regime, covering n-fold, tree-fold, 2-stage and multi-stage matrices.

Load-bearing premise

The dual algorithm's correctness rests on the sensitivity bound of Theorem 6, whose proof relies on a bijective encoding between the scaled IP and an auxiliary IP; that encoding must correctly handle negative entries, and as written it appears not to, so the bound is not actually established unless the encoding is repaired.

Editorial extensions

If this is right

  • Primal-treedepth separable convex IPs are solvable in g(td_P, ||A||_∞) n log(max(||u-l||_∞, ||b||_∞)) time, matching the n log||u-l||_∞ lower bound up to parameter dependence.
  • Dual-treedepth (tree-fold) IPs are solvable in g(td_D, ||A||_∞) n log n log(max(||u-l||_∞, ||b||_∞)) time, leaving at most a log n gap to the lower bound.
  • For n-fold and 2-stage matrices, where linear-time feasibility algorithms exist, the log||b||_∞ factor in both theorems can be removed, yielding running times that depend only on n and the bounds l, u.
  • The algorithms extend the sparse-update paradigm, previously applied mostly to linear n-fold ILPs, to general separable convex objectives.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The log n factor in the dual algorithm appears to be the price of refining one coordinate at a time; if the paper's conjectured stronger lower bound holds, that factor cannot be removed in the comparison model.
  • The convolution tree is a general dynamic subroutine: any setting where a small number of objective or bound entries change between queries could reuse it, for instance online or incremental integer programming.
  • A repaired encoding for negative entries in Lemma 4, such as a two's-complement style split, would likely restore the sensitivity bound; a genuine counterexample would force a different proof route for the dual algorithm.
  • The comparison-oracle lower bound does not constrain algebraic computation models, so strongly polynomial or division-based algorithms for some convex objective classes remain possible despite these results.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies separable convex integer programs min{f(x) | Ax = b, l ≤ x ≤ u, x ∈ Z^n} with a comparison oracle, in the regime where the constraint matrix A has small coefficients and small primal or dual treedepth. It proves an information-theoretic lower bound of n log ||u-l||_∞ comparison queries, gives a primal-treedepth algorithm matching this bound up to a parameter-dependent factor (Theorem 1), and gives a dual-treedepth algorithm with an extra log n factor (Theorem 2). The dual algorithm is built on a scaling scheme that refines one coordinate at a time, a new sensitivity bound (Theorem 6) controlling the ℓ1-distance between optima of I-scaled and J-scaled instances, and a new 'convolution tree' data structure supporting sparse updates. The central technical steps are an encoding of scaled IPs into an auxiliary 3n-variable IP (Lemma 4), a comparison between Graver norms of A and the auxiliary matrix (Lemma 3), and the resulting sensitivity theorem. The paper also proves a lower bound showing that the convolution tree's near-linear dependence on n is optimal in the comparison model.

Significance. If the technical gaps identified below are repaired, the paper would be a significant contribution: the unconditional lower bound cleanly explains why prior near-linear techniques for linear objectives cannot extend to separable convex objectives, and the two near-optimal algorithms, especially the convolution tree for the dual-treedepth case, are novel and likely to be useful beyond this specific problem. The paper is well written and carefully situates its results in a long line of work on block-structured integer programming. The lower-bound argument in Section 1.1 is sound and gives a clean benchmark. The main reason for not accepting the manuscript in its current form is that the sensitivity theorem on which the dual algorithm rests is not proven as written: Lemma 4's encoding is not a bijection, and Lemma 3 is false as stated. These are central, not cosmetic, but they appear to be local and repairable.

major comments (3)
  1. [Section 5, Lemma 4] The encoding between solutions of the I-scaled IP and the aux-I-IP is not a bijection for negative odd values. For i ∉ I and x_i = -3, the paper sets z_{n+i} = ceil(x_i/2) = -1 and z_i = -x_i mod 2 = 1, so the decoding z_i + 2z_{n+i} gives 1 + 2·(-1) = -1, not -3. The same defect occurs for every negative odd value. Consequently, the 'if and only if' optimality statement of Lemma 4 is not established, and the proof of Theorem 6 cannot legitimately invoke Theorem 5 through this encoding. A repair appears possible by using a balanced signed remainder z_i ∈ {-1,0,1} (e.g., z_i = -1 for x_i = -3, z_{n+i} = -1), but this must be worked out carefully together with the bounds of aux-I-IP.
  2. [Section 5, Lemma 3] Lemma 3 is false as stated. For A = [1 1], the vector v = (0,0,1,-1,2,-2) lies in G(¯A): it satisfies both blocks of ¯A v = 0 and it is conformally minimal under the sign constraints imposed by the bottom block. Its ℓ1-norm is 6, while g1(A) = 2, contradicting g1(¯A) ≤ 2g1(A). The proof breaks because the rounding rule for negative y_i can produce y'_i > y_i; for example, y_i = -1 and g'_i = -1 gives y'_i = min{0, max{-1, ceil(-1/2)}} = 0, which violates y' ⊑ y. Thus the second inequality in Theorem 6 and the asymptotic comparison with g1(A) are incorrect. The algorithm may still be salvaged by using g1(¯A) directly, since Lemma 5 gives tdD(¯A) = tdD(A)+1 and known bounds on g1(¯A) in terms of tdD(A) and ||A||∞ then suffice, but the theorem as written needs correction.
  3. [Section 6, proof of Theorem 2] The correctness of the one-coordinate-at-a-time refinement loop in Theorem 2 rests entirely on Theorem 6: each step j assumes that after changing the scaling set from [j,n] to [j+1,n], an optimum of the refined instance lies within ℓ1-distance 2g1(¯A) of the previous optimum, and this is what licenses solving the step as an ℓ1-IP with radius ρ = 2g1(¯A). Since Theorem 6's proof depends on the invalid Lemma 4 and on the false inequality from Lemma 3, the central guarantee of the dual algorithm is not established as written. This is a load-bearing gap, not a presentation issue. The defects appear repairable—a balanced encoding in Lemma 4 and a direct bound on g1(¯A) in place of Lemma 3—so I am not recommending rejection, but the proof must be corrected and re-verified before the main claims can be trusted.
minor comments (4)
  1. [Section 1.1] The sentence 'no strongly polynomial algorithm may exist' should be qualified: the lower bound holds in the comparison-oracle model, not for all models of computation.
  2. [Section 5, proof of Lemma 5] The proof of Lemma 5 refers to 'the set of rows of A which are non-zero in column i' and then says these rows lie on a root-leaf path in F, but the vertices of GD(A) are columns, not rows. The intended clique-path argument should be stated in terms of columns and their common rows.
  3. [Section 5, encoding paragraph] The expression 'z_i = -x_i mod 2' is ambiguous for negative integers; the paper should define the modular reduction used for negative values or, better, switch to a balanced remainder notation as suggested in the major comments.
  4. [Section 6, paragraph before Definition 6] The sentence 'a comparison oracle for fi's is implicit from the comparison oracle for fi' appears garbled; it should say that individual univariate functions fi can be queried by holding all other coordinates fixed, or clarify how the oracle is used to access fi.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the algorithms' claimed predictions are not fitted to their own inputs; the cited proximity, sensitivity, and lower-bound results are external or proven in-paper. The encoding gap in Lemma 4 is a correctness issue, not circularity.

full rationale

The paper's central claims are new algorithms for separable convex integer programs with primal or dual treedepth parameters. Theorem 1 is obtained by instantiating the scaling algorithm (Theorem 3) with an external proximity bound of Klein and Reuter (Proposition 4, [40]) and an external fixed-parameter algorithm of Eisenbrand et al. ([23, Lemma 8]); neither of these is derived from the paper's own conclusions, and the paper does not fit any parameter to the instances on which it is tested. Theorem 2 rests on a new sensitivity bound (Theorem 6), whose proof is attempted in the paper via an auxiliary IP encoding (Lemma 4) and an application of Theorem 5; the possible defect in Lemma 4's encoding of negative entries (e.g., x_i = -3 decoding to -1) would be an error in a proof step, not a circular reduction where an output is equivalent to an input by construction. The lower bound (n log ||u-l||_infinity) is an independent adversary argument based on comparison oracles and binary search, and it does not assume the algorithms' correctness. Self-citations to the authors' earlier block-structured IP papers [23, 34] supply standard prior results such as Graver-basis parameter bounds; these are external mathematical facts with stated assumptions, not unverified assertions of the present paper's conclusions. No fitted parameter is renamed as a prediction, no ansatz is smuggled in through self-citation, and no uniqueness theorem from the authors is invoked to forbid alternatives. The only substantive risk flagged in the paper is a missing/incorrect justification of the sensitivity bound, which is a correctness gap rather than circularity; therefore the circularity score is minimal.

Assumptions & free parameters 0 free parameters · 7 assumptions · 1 invented entities

The central results rest on the standard basis of integer programming (Graver bases, proximity, fixed-parameter branching) plus the new sensitivity machinery. No free parameters are fitted to data; the unspecified computable functions g absorb parameter dependence and are not fitted values. The only invented construction is the convolution tree, a formal data structure rather than a postulated empirical entity.

assumptions (7)
  • domain assumption The objective f is presented as a comparison oracle (Section 1.1).
    The information-theoretic lower bound and the algorithm time bounds are stated in this model; if f is given by a different representation the lower bound may fail.
  • standard math Klein-Reuter proximity bound: P_infinity(A) <= g'(td_P(A), ||A||_infinity) for primal treedepth (Proposition 4).
    Imported from Klein and Reuter [40]; used in Theorem 1 proof to bound the scaling radius.
  • standard math Graver basis positive sum property (Proposition 3).
    Used in Theorem 5 and elsewhere; standard result from Onn [55].
  • standard math The branching algorithm of Eisenbrand et al. [23, Lemma 8] solves each small-width subinstance in time td_P(A)^2(2rho+1)^{td_P(A)} n.
    Imported result used in Theorem 1 proof; correctness is not re-derived in the paper.
  • standard math The matrix bar A = [A 2A 0; I 2I -I] admits a td-decomposition with height and topological height increased by 1 (Lemma 5).
    Proven in the paper; used to keep the dual algorithm's parameter dependence computable.
  • standard math Separable convex superadditivity (Proposition 1).
    Quoted from De Loera et al. [16]; used in Lemma 2 and Theorem 5 proofs.
  • domain assumption Univariate convex minimization over an integer interval requires log(range) comparisons with a comparison oracle.
    Gives the n log(||u-l||_infinity) lower bound for the box case; elementary adversary argument.
invented entities (1)
  • Convolution tree (Definition 6)
    purpose: Dynamic data structure that maintains an optimal solution to ell-1-IP under single-coordinate updates, enabling sparse updates in the dual algorithm.
    A formal algorithmic construct fully specified in the paper; it has no external empirical signature but its correctness is intended to be proven internally.

how reviews work

0 comments
Cite this review

Pith. "Pith review of (Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs." pith.science (2026). https://pith.science/paper/LADT3RGX

@misc{pith2026250522212,
  author       = {Pith},
  title        = {Pith review of: (Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LADT3RGX}},
  note         = {Machine review of arXiv:2505.22212}
}
abstract

We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mathbf{b}, \, \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}, \, \mathbf{x} \in \mathbb{Z}^n\}$. The number of variables $n$ is a variable part of the input, and we consider the regime where the constraint matrix $A$ has small coefficients $\|A\|_\infty$ and small primal or dual treedepth $\mathrm{td}_P(A)$ or $\mathrm{td}_D(A)$, respectively. Equivalently, we consider block-structured matrices, in particular $n$-fold, tree-fold, $2$-stage and multi-stage matrices. We ask about the possibility of near-linear time algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of $n \log \|\mathbf{u}-\mathbf{l}\|_\infty$, where $\mathbf{l}, \mathbf{u}$ are the vectors of lower and upper bounds. Our first result is that with parameters $\mathrm{td}_P(A)$ and $\|A\|_\infty$, this lower bound can be matched (up to dependency on the parameters). Second, with parameters $\mathrm{td}_D(A)$ and $\|A\|_\infty$, the situation is more involved, and we design an algorithm with time complexity $g(\mathrm{td}_D(A), \|A\|_\infty) n \log n \log \|\mathbf{u}-\mathbf{l}\|_\infty$ where $g$ is some computable function. We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal. Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure.

Figures

Figures reproduced from arXiv: 2505.22212 by the authors.

Figure 1
Figure 1. On the left a schematic depiction of a multi-stage stochastic matrix with [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The situation of Lemma 2: the feasible region between lower and upper bounds is the light grey rectangle; the dark grey rectangle marks the region of vectors which, when translated to zˆ, are conformal to xˆ − zˆ. The picture makes it clear that g and g¯ are conformal to xˆ − zˆ, and that the identity xˆ = zˆ + g + g¯ holds. 3.2 Scaling Algorithm for IP As a 2 k -scaled instance is also a 2-scaled instance of a 2 k−… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

60 extracted references · 59 canonical work pages

  1. [1]

    INFORMS J

    Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming. INFORMS J. Comput.32(2), 473–506 (2020)

    work page 2020

  2. [2]

    Prentice Hall, Inc., Englewood Cliffs, New Jersey (1993)

    Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Inc., Englewood Cliffs, New Jersey (1993)

    work page 1993

  3. [3]

    European Journal of Operational Research190(1), 1–21 (2008)

    Alumur, S.A., Kara, B.Y.: Network hub location problems: The state of the art. European Journal of Operational Research190(1), 1–21 (2008)

    work page 2008

  4. [4]

    Anderson, R., Huchette, J., Ma, W., Tjandraatmadja, C., Vielma, J.P.: Strong mixed-integer programming formulations for trained neural networks. Math. Program.183(1), 3–39 (2020)

    work page 2020

  5. [5]

    Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. J. Comb. Optim.22(1), 78–96 (2011)

    work page 2011

  6. [6]

    Aschenbrenner, M., Hemmecke, R.: Finiteness theorems in stochastic integer programming. Found. Comput. Math.7(2), 183–227 (2007)

    work page 2007

  7. [7]

    Springer (2008)

    de Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational geometry: algorithms and applications, 3rd Edition. Springer (2008)

    work page 2008

  8. [8]

    The Annals of Statistics44(2), 813–852 (2016)

    Bertsimas, D., King, A., Mazumder, R.: Best subset selection via a modern optimization lens. The Annals of Statistics44(2), 813–852 (2016)

    work page 2016

Show all 60 references
  1. [9]

    In: Automated Planning and Scheduling, ICAPS 2005

    van den Briel, M., Vossen, T., Kambhampati, S.: Reviving integer pro- gramming approaches for AI planning: A branch-and-cut framework. In: Automated Planning and Scheduling, ICAPS 2005. Proceedings. pp. 310–319. AAAI (2005)

    2005

  2. [10]

    In: Mohar, B., Shinkar, I., O’Donnell, R

    Chen, L., Kyng, R., Liu, Y.P., Meierhans, S., Gutenberg, M.P.: Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, s-t shortest path, and minimum-cost flow. In: Mohar, B., Shinkar, I., O’Donnell, R. (eds.) Proceedings of the 56th Annual ACM Symposium o...

    2024

  3. [11]

    In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Den- ver, CO, USA, October 31 - November 3, 2022

    Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S.: Maximum flow and minimum-cost flow in almost-linear time. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Den- ver, CO, USA, October 31 - November 3, 2022. pp. 612–623. IEEE (2022)

    2022

  4. [12]

    In: 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017

    Chen, L., Marx, D., Ye, D., Zhang, G.: Parameterized and approximation results for scheduling with a low rank processing time matrix. In: 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017. LIPIcs, vol. 66, pp. 22:1–22:14. Schloss Dagstuhl — Leibniz-Zentrum ...

    2017

  5. [13]

    In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

    Cslovjecsek, J., Eisenbrand, F., Hunkenschröder, C., Rohwedder, L., Weis- mantel, R.: Block-structured integer and linear programming in strongly polynomial and near linear time. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. pp. 1666–1681. SIAM (2021) 2...

    2021

  6. [14]

    In: 29th Annual European Symposium on Algorithms, ESA 2021

    Cslovjecsek, J., Eisenbrand, F., Pilipczuk, M., Venzin, M., Weismantel, R.: Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity. In: 29th Annual European Symposium on Algorithms, ESA 2021. LIPIcs, vol. 204, pp. 33:1–33:14....

    2021

  7. [15]

    In: Woodruff, D.P

    Cslovjecsek, J., Koutecký, M., Lassota, A., Pilipczuk, M., Polak, A.: Param- eterized algorithms for block-structured integer programs with large entries. In: Woodruff, D.P. (ed.) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA...

    2024

  8. [16]

    De Loera, J.A., Hemmecke, R., Köppe, M.: Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MOS-SIAM Series on Optimization, vol. 14. SIAM (2013)

    2013

  9. [17]

    Discrete Optimization5(2), 231–241 (2008), in Memory of George B

    De Loera, J.A., Hemmecke, R., Onn, S., Weismantel, R.:N-fold integer programming. Discrete Optimization5(2), 231–241 (2008), in Memory of George B. Dantzig

    2008

  10. [18]

    In: Woodruff, D.P

    Dong, S., Goranci, G., Li, L., Sachdeva, S., Ye, G.: Fast algorithms for separable linear programs. In: Woodruff, D.P. (ed.) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024. pp. 3558–3604. SIAM (2024)

    2024

  11. [19]

    In: Khuller, S., Williams, V.V

    Dong, S., Lee, Y.T., Ye, G.: A nearly-linear time algorithm for linear pro- grams with small treewidth: a multiscale representation of robust central path. In: Khuller, S., Williams, V.V. (eds.) STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, ...

    2021

  12. [20]

    In: 45th International Colloquium on Au- tomata, Languages, and Programming, ICALP 2018

    Eisenbrand, F., Hunkenschröder, C., Klein, K.: Faster algorithms for integer programs with block structure. In: 45th International Colloquium on Au- tomata, Languages, and Programming, ICALP 2018. LIPIcs, vol. 107, pp. 49:1–49:13. Schloss Dagstuhl — Leibniz-Zentrum für Informa...

    2018

  13. [21]

    CoRRabs/1904.01361 (2019)

    Eisenbrand, F., Hunkenschröder, C., Klein, K., Koutecký, M., Levin, A., Onn, S.: An algorithmic theory of integer programming. CoRRabs/1904.01361 (2019)

    2019 arXiv

  14. [22]

    Eisenbrand, F., Hunkenschröder, C., Klein, K., Koutecký, M., Levin, A., Onn, S.: Reducibility bounds of objective functions over the integers. Oper. Res. Lett.51(6), 595–598 (2023)

    2023

  15. [23]

    Mathe- matics of Operations Research0(0) (2024)

    Eisenbrand, F., Hunkenschröder, C., Klein, K.M., Koutecký, M., Levin, A., Onn, S.: Sparse integer programming is fixed-parameter tractable. Mathe- matics of Operations Research0(0) (2024)

    2024

  16. [24]

    CoRRabs/2501.02347 (2025)

    Eisenbrand, F., Rothvoss, T.: A parameterized linear formulation of the integer hull. CoRRabs/2501.02347 (2025)

    2025

  17. [25]

    Floudas, C.A., Lin, X.: Mixed integer linear programming in process schedul- ing: Modeling, algorithms, and applications. Ann. Oper. Res.139(1), 131–162 (2005)

    2005

  18. [26]

    Gavenčiak, T., Koutecký, M., Knop, D.: Integer programming in param- eterized complexity: Five miniatures. Discret. Optim.44(Part), 100596 (2022) (Near)-Optimal Algorithms for Sparse Separable Convex IPs 27

    2022

  19. [27]

    Graver, J.E.: On the foundations of linear and integer linear programming i. Math. Program9(1), 207–226 (1975)

    1975

  20. [28]

    Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combina- torial optimization, Algorithms and Combinatorics, vol. 2. Springer-Verlag, Berlin, second edn. (1993)

    1993

  21. [29]

    Mathematical Programming145(1-2, Ser

    Hemmecke, R., Köppe, M., Weismantel, R.: Graver basis and proximity tech- niques for block-structured separable convex integer minimization problems. Mathematical Programming145(1-2, Ser. A), 1–18 (2014)

    2014

  22. [30]

    Hemmecke, R., Onn, S., Romanchuk, L.:n-fold integer programming in cubic time. Math. Program.137(1-2), 325–341 (2013)

    2013

  23. [31]

    Mathematical Programming94, 323–341 (2003)

    Hemmecke, R., Schultz, R.: Decomposition of test sets in stochastic integer programming. Mathematical Programming94, 323–341 (2003)

    2003

  24. [32]

    Hochbaum, D.S.: Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Math. Oper. Res19(2), 390–409 (1994)

    1994

  25. [33]

    Journal of the ACM37(4), 843–862 (1990)

    Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder than linear optimization. Journal of the ACM37(4), 843–862 (1990)

    1990

  26. [34]

    In: Vygen, J., Byrka, J

    Hunkenschröder, C., Klein, K., Koutecký, M., Lassota, A., Levin, A.: Tight lower bounds for block-structured integer programs. In: Vygen, J., Byrka, J. (eds.) Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Wroclaw, Poland, July 3...

    2024

  27. [35]

    Jansen, K., Klein, K., Lassota, A.: The double exponential runtime is tight for 2-stage stochastic ILPs. Math. Program.197(2), 1145–1172 (2023)

    2023

  28. [36]

    Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-IP: new PTAS results for scheduling with setup times. Math. Program.195(1), 367–401 (2022)

    2022

  29. [37]

    Jansen, K., Lassota, A., Rohwedder, L.: Near-linear time algorithm forn-fold ILPs via color coding. SIAM J. Discret. Math.34(4), 2282–2299 (2020)

    2020

  30. [38]

    In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D

    Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computa- tions, The IBM Research Symposia Series, pp. 85–103. Springer (1972)

    1972

  31. [39]

    Klein, K.: About the complexity of two-stage stochastic IPs. Math. Program. 192(1), 319–337 (2022)

    2022

  32. [40]

    In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

    Klein, K., Reuter, J.: Collapsing the tower — On the complexity of multi- stage stochastic IPs. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. pp. 348–358. SIAM (2022)

    2022

  33. [41]

    CoRRabs/1909.07326 (2019)

    Knop, D., Koutecký, M., Levin, A., Mnich, M., Onn, S.: Multitype integer monoid optimization and applications. CoRRabs/1909.07326 (2019)

    2019 arXiv

  34. [42]

    Mathematical Programming200(1), 199–227 (Jun 2023)

    Knop, D., Koutecký, M., Levin, A., Mnich, M., Onn, S.: High-multiplicity n-fold ip via configuration lp. Mathematical Programming200(1), 199–227 (Jun 2023)

    2023

  35. [43]

    Knop, D., Koutecký, M.: Scheduling meetsn-fold integer programming. J. Sched. 21(5), 493–503 (2018) 28 C. Hunkenschröder et al

    2018

  36. [44]

    Knop, D., Koutecký, M., Levin, A., Mnich, M., Onn, S.: Parameterized complexity of configuration integer programs. Oper. Res. Lett.49(6), 908– 913 (2021)

    2021

  37. [45]

    Knop, D., Koutecký, M., Levin, A., Mnich, M., Onn, S.: High-multiplicity N-fold IP via configuration LP. Math. Program.200(1), 199–227 (2023)

    2023

  38. [46]

    Knop, D., Koutecký, M., Mnich, M.: Combinatorialn-fold integer program- ming and applications. Math. Program.184(1), 1–34 (2020)

    2020

  39. [47]

    ACM Trans

    Knop, D., Koutecký, M., Mnich, M.: Voting and bribing in single-exponential time. ACM Trans. Economics and Comput.8(3), 12:1–12:28 (2020)

    2020

  40. [48]

    ACM Trans

    Knop, D., Pilipczuk, M., Wrochna, M.: Tight complexity lower bounds for integer linear programming with few constraints. ACM Trans. Comput. Theory 12(3), 19:1–19:19 (2020)

    2020

  41. [49]

    INFORMS J

    Knueven, B., Ostrowski, J., Watson, J.: On mixed-integer programming formulations for the unit commitment problem. INFORMS J. Comput.32(4), 857–876 (2020)

    2020

  42. [50]

    In: Proc

    Koutecký, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: Proc. ICALP 2018. Leibniz Int. Proc. Informatics, vol. 107, pp. 85:1–85:14 (2018)

    2018

  43. [51]

    Lau, L.C., Ravi, R., Singh, M.: Iterative methods in combinatorial optimiza- tion, vol. 46. Cambridge University Press (2011)

    2011

  44. [52]

    European Journal of Operational Research141(2), 241–252 (2002)

    Lodi, A., Martello, S., Monaci, M.: Two-dimensional packing problems: A survey. European Journal of Operational Research141(2), 241–252 (2002)

    2002

  45. [53]

    Murota, K., Tamura, A.: Proximity theorems of discrete convex functions. Math. Program.99(3), 539–562 (2004)

    2004

  46. [54]

    Norton, C.H., Plotkin, S.A., Tardos, É.: Using separation algorithms in fixed dimension. J. Algorithms13(1), 79–98 (1992)

    1992

  47. [55]

    Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010)

    Onn, S.: Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010)

    2010

  48. [56]

    In: Esparza, J., Fraigniaud, P., Husfeldt, T., Kout- soupias, E

    Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: A faster parameterized algorithm for treedepth. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Kout- soupias, E. (eds.) Proceedings Part I of the 41st International Colloquium on Automata, Languages, and Programming, ICAL...

    2014

  49. [57]

    Statistica Neerlandica50(3), 404–416 (1996)

    Schultz, R., Stougie, L., van der Vlerk, M.H.: Two-stage stochastic integer programming: a survey. Statistica Neerlandica50(3), 404–416 (1996)

    1996

  50. [58]

    (eds.): The Vehicle Routing Problem

    Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2001)

    2001

  51. [59]

    In: International Joint Conference on Artificial Intelligence, IJCAI 99

    Vossen, T., Ball, M.O., Lotem, A., Nau, D.S.: On the use of integer program- ming models in AI planning. In: International Joint Conference on Artificial Intelligence, IJCAI 99. Proceedings. pp. 304–309. Morgan Kaufmann (1999)

    1999

  52. [2024]

    pp. 740–751. SIAM (2024)

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.