A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

Meirav Zehavi; Pallavi Jain; Sanjay Seetharaman; Sushmita Gupta

REVIEW 3 major objections 4 minor 32 references

A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

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

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

Pith's one-line read This paper proves that combinatorial n-fold ILPs with arbitrary top blocks can be solved directly, without LP relaxations or Graver augmentation, in time $O(nt\,(n\Delta(n+1+4r))^r q)$, and that the inequality-tolerant version runs in…

desk verdict The P1 algorithm is sound and clearly written, but it duplicates Rohwedder's ICALP 2025 result, and the P2-to-P1 reduction that drives the applications has a false slack bound, so the paper's secondary claims are not established. read the letter →

arxiv 2507.03766 v2 pith:V4TYOXUA submitted 2025-07-04 cs.DS

Sushmita Gupta , Pallavi Jain , Sanjay Seetharaman , Meirav Zehavi This is my paper · ORCID

classification cs.DS MSC 90C1068Q2568W40

keywords n-foldintegerprogrammingcombinatorialILPSteinitzlemmaparameterizedalgorithmsLobbyingClosestStringblock-structuredshortestpath

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

This paper presents a direct, non-iterative algorithm for combinatorial $n$-fold ILPs, a class of integer programs where each of $n$ bricks shares a single all-ones row block and the top blocks may differ. The algorithm never solves an LP relaxation and never performs Graver-basis augmentation; instead, it reorders the columns inside each brick so that every partial sum stays close to its proportional share, and then finds an optimal solution as a shortest path in a layered directed acyclic graph. The claimed running time for the equality-only form is $O(nt\,(n\Delta(n+1+4r))^r\cdot q)$, where $q$ is the sum of the last $n$ right-hand-side entries. A reduction from a natural inequality-constrained form is also given, with running time $O(qrt\,((n+1)\Delta(n+2+4r))^{r+1})$. These bounds yield $2^{O(m^2)}$ and $2^{O(k^2)}$ algorithms for Lobbying and Binary Closest String, improving on earlier $m^{O(m^2)}$ and $k^{O(k^2)}$ dependencies.

What carries the argument

The engine is the Steinitz lemma, which says that vectors summing to a target can be reordered so that every partial sum stays within a dimension-dependent constant of the proportional line; the paper uses a corollary that bounds each coordinate by $2r\Delta$. The new one-row balancing lemma (Lemma 4) greedily fills a sequence of block indices so that for every block $i$ and every prefix $j$, the imbalance $\operatorname{occ}(i,j) - (j/q)b^{(i)}$ lies between $-n$ and $+1$. Combining these two bounds confines each coordinate of the running partial-sum vector to an interval of width $O(n\Delta(n+r))$, which keeps the layered graph small: at most $1+q(n\Delta(n+1+4r))^r$ vertices. A shortest path in that graph is the optimal solution.

What would settle it

Take a Lobbying instance with at least one column where the number of missing ones $g_k$ is positive, so the right-hand side $b^{(0)}[k]=-g_k$ is negative. For any feasible solution, the slack $b^{(0)}[k]-A[k,:]y$ is nonnegative, while the bound $2\Delta\,b^{(0)}[k]$ is negative; checking whether the Section 4.1 construction still produces a feasible $(P1)$ point would show whether Corollary 7's reduction is sound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: the integer program $\min\{c^\top x \mid Ax=b,\ x\in\mathbb{Z}^{nt}_{\ge 0}\}$, with diagonal blocks $D=(1,\dots,1)$ and arbitrary $r\times t$ top blocks $T^{(1)},\dots,T^{(n)}$, can be solved in time $O(nt\,(n\Delta(n+1+4r))^r\cdot q)$ where $q=\sum_{i} b^{(i)}$. The proof is constructive: any optimal solution gives a multiset of columns from the top blocks; Lemma 4 greedily orders the block labels so that each symbol's imbalance stays between $-n$ and $+1$, and Lemma 5 applies the Steinitz lemma inside each block so that every coordinate of every partial sum stays within $O(n\Delta(n+r))$ of the proportional line. The algorithm then builds a graph whose vertices are the bounded partial-sum vectors, and a shortest path between the zero vector and $b^{(0)}$ corresponds exactly to an optimal solution. The paper further claims that programs with inequalities in the globally uniform and locally uniform constraints reduce to $(P1)$ with no asymptotic loss, giving Corollary 7 and the applications to Lobbying and $\delta$-Multi Strings.

Load-bearing premise

The reduction from inequality-constrained programs $(P2)$ to the equality form $(P1)$ assumes that the slack in each globally uniform constraint is at most $2\Delta$ times that constraint's right-hand side; when a globally uniform constraint is a lower bound, the right-hand side can be negative while the slack is nonnegative, so the assumption is not automatically satisfied.

Editorial extensions

If this is right

For the equality form $(P1)$, the algorithm runs in $O(nt\,(n\Delta(n+1+4r))^r\, q)$ time with no LP relaxation and no Graver-augmentation steps.
For the inequality form $(P2)$, the Section 4.1 reduction gives $O(qrt\,((n+1)\Delta(n+2+4r))^{r+1})$ time.
Lobbying can be solved in $2^{O(m^2)}\cdot w^{O(1)}$ time, improving on the earlier $m^{O(m^2)}$ dependency.
$\delta$-Multi Strings with a character-wise wildcard-compatible distance is solvable in $(\Delta k)^{O(k)}|\Sigma|^{O(k^2)}L^{O(1)}$, and Binary Closest String in $2^{O(k^2)}L^{O(1)}$ time, matching the lower bound hypothesized in [30].
The Equitable Coloring parameterized by vertex cover number $k$ is solvable in $2^{O(k^2)}|V(G)|^{O(1)}$ time in the appendix construction.

Reading between the lines

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

Editorial inference: the greedy balancing lemma is a discrepancy-style statement for sequences, and the same bounded-imbalance idea could be applied to other block-structured ILPs whose diagonal blocks are not all-ones, potentially replacing augmentation loops with a single reordering step.
Editorial inference: the linear dependence on $q$ means the practical advantage over LP-based algorithms depends on whether $q$ stays comparable to $nt$; for high-multiplicity instances with large $q$, the bound is weaker than the near-linear $nt\,\mathrm{polylog}$ algorithms it competes with.
Editorial inference: if the Section 4.1 slack bound fails, as it does when a globally uniform constraint is a lower bound with negative right-hand side, the reduction to $(P1)$ may reject feasible solutions; a modified construction or an additional argument would be needed to keep the Lobbying and Binary Closest String running times intact.
Editorial inference: the shortest-path formulation is objective-agnostic, so the same graph would likely handle separable convex objectives by replacing edge weights with convex increments per column, extending the method beyond linear objectives.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Brief take: the core P1 algorithm is real and clean, but it is not new—the authors say so themselves—and the P2-to-P1 reduction that powers the Lobbying and Closest String results contains a false bound, so those running times are not established as written. The Steinitz-based balancing argument (Lemmas 4 and 5) is a genuinely nice way to avoid augmentation and LP relaxation for the equality case. The graph DP is standard but carefully presented, and the P1 part should be reproducible from the pseudocode. The paper also does the right thing in flagging Rohwedder's ICALP 2025 paper with identical running times and similar techniques. That is honest scholarship; it just means the main theorem is not a novel result. The serious problem sits in Section 4.1. The reduction from P2 to P1 asserts that the slack in a globally uniform constraint, x(n+1)_{t+1+k} = b(0)[k] - A[k,:]y, is at most 2\Delta b(k). That is false in general: for an inequality x <= M with x = 0, the slack is M, and if T can contain negative entries (as in Lobbying, where the matrix has -B), the slack can exceed any bound derived from the RHS. The stress-test counterexample is valid: with x <= M and x <= L and M large, the construction forces the slack M to be absorbed by a block of size 2L, so a feasible P2 solution maps to an infeasible P1 instance. Since Corollary 7 and the Lobbying/Closest String theorems rely on this reduction, those claims are not established. Additionally, Lemma 4's proof has an unjustified 'By Algorithm 1, we have imb(e,q) >= 0' line, which is probably repairable but needs a fix. The Lobbying application also has an inconsistent definition of q, though that is minor by comparison. Who is this for? People working on block-structured ILP and parameterized algorithms for social choice and string problems. The P1 part is a useful expository note, but as a paper claiming new running times, it currently overreaches because of Section 4.1. If the authors fix the slack bound—perhaps by setting b(n+1) to a sum of positive parts or by a different construction—the applications would be worth taking seriously. As is, I would recommend sending this to peer review, not desk rejection, but with a clear message that the applications section needs substantial rework and the current corollaries should not be accepted until the reduction is repaired.

Referee Report

3 major / 4 minor

Summary. The paper studies a class of combinatorial n-fold integer linear programs in which the diagonal blocks are all-ones row vectors and the top blocks may differ across blocks. The main algorithm first balances a one-row matrix of block indices (Lemma 4), then uses the Steinitz lemma to bound the partial sums of an associated column ordering (Lemma 5), and finally reduces the problem to a shortest-path computation in a layered graph. Theorem 1 claims a running time of O(nt·(nΔ(n+1+4r))^r·q), where q is the sum of the local right-hand sides. Section 4 extends the algorithm to programs with inequality constraints (P2) and derives applications to Lobbying, δ-Multi Strings / Closest String, and Equitable Coloring.

Significance. If correct, the paper would give a conceptually simple, LP-free, non-augmenting algorithm for a natural class of n-fold ILPs, and it would improve the parameter dependence for Lobbying and Binary Closest String to 2^{O(m^2)} and 2^{O(k^2)}, respectively. The proof structure is transparent, the partial-sum bounds are explicit, and the shortest-path formulation is elegant. However, the reduction in Section 4.1 contains false claims, so Corollary 7 and the application theorems are not established as written. The core Theorem 1 is plausible, but the proof of Lemma 4 needs repair before the main result can be considered fully sound.

major comments (3)

[Section 4.1, definition of ψ] The text states: 'Observe that ψ/2 is strictly larger than the maximum value the objective function in (P2) can take.' This is false. Since each local constraint is a ≤ constraint, every feasible solution satisfies Σ_j x(i)_j ≤ b(i) for each i, so c^T x can be as large as ∥c∥∞·Σ_i b(i), which may be n times larger than ψ/2 = 1 + ∥c∥∞·max_i b(i). Consequently, the 'other direction' of the reduction, which discards P1 solutions of cost at least ψ/2 as evidence that P2 is infeasible, is invalid.
[Section 4.1, slack bound and construction of b(n+1)] The reduction sets b(n+1) = 2rΔ·max_i b(i) and asserts that the global slack x(n+1)_{t+1+k} = b(0)[k] − A[k,:]y is 'at most 2Δ·b(k)'. This claim is false in general. For example, consider P2 given by min x subject to x ≤ M, x ≤ L, x ∈ Z_{\ge 0}, with M > 2L and r = 1, Δ = 1. At the feasible solution x = 0, the slack in x ≤ M equals M, which exceeds b(n+1) = 2L; the constructed P1 then has no solution of cost below ψ/2 even though P2 is feasible. The same phenomenon occurs in the Lobbying formulation, where b(0)[k] = −g_k is negative while the slack can be nonnegative and large. Thus the reduction from P2 to P1 is not an equivalence, and Corollary 7 together with Theorems 8–11 are not established as stated.
[Section 3.1, proof of Lemma 4] The proof of Lemma 4 contains an unjustified assertion in its final paragraph: 'By Algorithm 1, we have that imb_{Mσ}(e,q) ≥ 0 for each e ∈ [n]\{e′}'. This is false when some symbol has zero occurrences, because such a symbol has imbalance identically 0 and can be selected by an arbitrary tie-breaking in the arg min, producing a sequence that is not a permutation of M. The earlier upper-bound argument also asserts that the greedy choice implies all imbalances are positive, which does not follow from the displayed inequalities. The lemma may be true, but the proof needs to be repaired, for instance by restricting the arg min to symbols with remaining occurrences and giving a correct invariant.

minor comments (4)

[Section 3.3, Construction 1] The vertex definition says 'For each j ∈ [n]', but the vertices are indexed by positions in the sequence, so this should read 'For each j ∈ [q]'.
[Section 4.1, notation for ψ] The quantity ∥c∥∞ should be the maximum absolute value of the objective coefficients; as written, negative objective coefficients would make the bound on ψ/2 meaningless.
[Section 3.2, proof of Lemma 5] The proof divides by b(i) in the expressions occ(i,j)/b(i); if b(i) = 0, these terms are undefined, and the proof should state that blocks with b(i) = 0 are omitted.
[Section 5.1, Equitable Coloring formulation] The second size constraint says 'if j ∈ {a,...,h}', but the two cases should partition the color classes; the second range is likely {a+1,...,h}.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main algorithm is a self-contained derivation from the external Steinitz Lemma and its standard generalization.

full rationale

The paper's central claim, Theorem 1, is derived from external results: the Steinitz Lemma (Proposition 2) and the Eisenbrand--Weismantel generalization (Corollary 3). The balancing lemma (Lemma 4) is proved directly via a greedy counting argument with an explicit exchange-style proof. The partial-sum bound (Lemma 5) applies Corollary 3 to each block and then combines the bounded imbalances with the column-sum structure; no target quantity is used to define the algorithm's inputs. The DP graph in Construction 1 is built from the explicit numerical bounds proved in Lemma 5, and the path-cost equivalence is a standard reachability argument. There are no fitted parameters, no prediction derived from a fitted subset of data, and no load-bearing self-citation chain: the authors' citations to Knop et al. and Rohwedder are contextual and comparative, not justifications of the main theorem. The possible flaw in Section 4.1 concerning the slack bound is a mathematical correctness concern about the inequality-to-equality reduction, not a circularity: the slack variables are defined from the constraints, but the asserted bound is an empirical mathematical claim rather than an identity forced by definition. Therefore the paper does not exhibit any of the enumerated circularity patterns, and the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's derivation is largely self-contained, deriving the algorithm from the Steinitz Lemma. The only questionable axiom is the slack bound in Section 4.1, which is false as stated and is load-bearing for the P2 generalization.

assumptions (4)

standard math Steinitz Lemma (Proposition 2): any zero-sum vectors of norm at most 1 can be reordered so all partial sums stay within a ball of radius d.
Used to bound partial sums in Lemma 5; standard result cited as [32,15].
standard math Eisenbrand-Weismantel generalization (Corollary 3): partial sums of vectors with sum s and entries bounded by Delta can be kept within 2*Delta*d of the proportional sum.
Used to reorder each block V(i); standard result cited as [12].
ad hoc to paper Global slack bound: each globally uniform constraint's slack x(n+1)_{t+1+k} = b(0)[k] - A[k,:]y is at most 2*Delta*b(0)[k].
Assumed in Section 4.1 to set b(n+1) = 2*r*Delta*max_i b(i); false in general, so the P2 reduction is not justified as stated.
domain assumption Local RHS entries b(i) are non-negative for feasible instances.
q = sum b(i) is used as the number of vectors in the sequence; negative b(i) would make the local equality constraints infeasible with non-negative variables.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma." pith.science (2026). https://pith.science/paper/V4TYOXUA

@misc{pith2026250703766,
  author       = {Pith},
  title        = {Pith review of: A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V4TYOXUA}},
  note         = {Machine review of arXiv:2507.03766}
}

abstract

We present an algorithm for a class of $n$-fold ILPs whose existing algorithms in literature are often either (1) based on the \textit{augmentation framework} where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; or (2) require solving a linear relaxation of the program; or (3) are based on decomposition/proximity based arguments. Combinatorial $n$-fold ILPs is a class of $n$-fold ILPs introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves combinatorial $n$-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma. Depending on the structure of the input ILP, we also improve upon the existing algorithms in the literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 20 canonical work pages

[1]

Pitsoulis

Gautam Appa, Bal \' a zs Kotnyek, Konstantinos Papalamprou, and Leonidas S. Pitsoulis. Optimization with binet matrices. Oper. Res. Lett. , 35(3):345--352, 2007. https://doi.org/10.1016/J.ORL.2006.04.003 doi:10.1016/J.ORL.2006.04.003

work page doi:10.1016/j.orl.2006.04.003 2007
[2]

A strongly polynomial algorithm for bimodular integer linear programming

Stephan Artmann, Robert Weismantel, and Rico Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 , pages 1206--1219. ACM , 2017. https://doi.org/10.1145/3055399.3055473 doi:10.1...

arXiv 2017
[3]

On the Power of Linear Dependencies , pages 31--45

Imre B \'a r \'a ny. On the Power of Linear Dependencies , pages 31--45. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. https://doi.org/10.1007/978-3-540-85221-6_1 doi:10.1007/978-3-540-85221-6_1

work page doi:10.1007/978-3-540-85221-6_1 2008
[4]

Woeginger

Robert Bredereck, Jiehua Chen, Sepp Hartung, Stefan Kratsch, Rolf Niedermeier, Ondrej Such \' y , and Gerhard J. Woeginger. A multivariate complexity analysis of lobbying in multiple referenda. J. Artif. Intell. Res. , 50:409--446, 2014. https://doi.org/10.1613/JAIR.4285 doi:10.1613/JAIR.4285

work page doi:10.1613/jair.4285 2014
[5]

On complexity of lobbying in multiple referenda

Robin Christian, Mike Fellows, Frances Rosamond, and Arkadii Slinko. On complexity of lobbying in multiple referenda. Review of Economic Design , 11(3):217--224, Nov 2007. https://doi.org/10.1007/s10058-007-0028-1 doi:10.1007/s10058-007-0028-1

doi:10.1007/s10058-007-0028-1 2007
[6]

Block-structured integer and linear programming in strongly polynomial and near linear time

Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschr \" o der, Lars Rohwedder, and Robert Weismantel. Block-structured integer and linear programming in strongly polynomial and near linear time. In D \' a niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pag...

work page doi:10.1137/1.9781611976465.101 2021
[7]

Parameterized algorithms for block-structured integer programs with large entries

Jana Cslovjecsek, Martin Kouteck \' y , Alexandra Lassota, Michal Pilipczuk, and Adam Polak. Parameterized algorithms for block-structured integer programs with large entries. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 , pages 740--751. SIAM , 2024. https://doi.org/10.1137/1.9781611977912.29 ...

work page doi:10.1137/1.9781611977912.29 2024
[8]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

doi:10.1007/978-3-319-21275-3 2015

Show all 32 references

[9]

Faster algorithms for integer programs with block structure

Friedrich Eisenbrand, Christoph Hunkenschr \" o der, and Kim - Manuel Klein. Faster algorithms for integer programs with block structure. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , volume 107 of LIPIcs , pages 49:1--49:13. Schloss Da...

2018 doi
[10]

An algorithmic theory of integer programming

Friedrich Eisenbrand, Christoph Hunkenschr \" o der, Kim - Manuel Klein, Martin Kouteck \' y , Asaf Levin, and Shmuel Onn. An algorithmic theory of integer programming. CoRR , abs/1904.01361, 2019. URL: http://arxiv.org/abs/1904.01361, https://arxiv.org/abs/1904.01361 arXiv:1904.01361

1904 arXiv
[11]

Sensitivity, proximity and FPT algorithms for exact matroid problems

Friedrich Eisenbrand, Lars Rohwedder, and Karol Wegrzycki. Sensitivity, proximity and FPT algorithms for exact matroid problems. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024 , pages 1610--1620. IEEE , 2024. https://doi.org/10.1109/FOCS61266.2024....

2024
[12]

Proximity results and faster algorithms for integer programming using the S teinitz L emma

Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the S teinitz L emma. ACM Trans. Algorithms , 16(1):5:1--5:14, 2020. https://doi.org/10.1145/3340322 doi:10.1145/3340322

2020 doi
[13]

Golovach, and Jan Kratochv \' l

Jir \' Fiala, Petr A. Golovach, and Jan Kratochv \' l. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theor. Comput. Sci. , 412(23):2513--2523, 2011. https://doi.org/10.1016/J.TCS.2010.10.043 doi:10.1016/J.TCS.2010.10.043

2011 doi
[14]

Guilherme C. M. Gomes, Matheus R. Guedes, and Vin \' cius Fernandes dos Santos. Structural parameterizations for equitable coloring: Complexity, FPT algorithms, and kernelization. Algorithmica , 85(7):1912--1947, 2023. https://doi.org/10.1007/S00453-022-01085-W doi:10.1007/S00...

1912 doi
[15]

V. S. Grinberg and S. V. Sevast'yanov. Value of the steinitz constant. Functional Analysis and Its Applications , 14(2):125--126, Apr 1980. https://doi.org/10.1007/BF01086559 doi:10.1007/BF01086559

1980 doi
[16]

n-fold integer programming in cubic time

Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-fold integer programming in cubic time. Math. Program. , 137(1-2):325--341, 2013. URL: https://doi.org/10.1007/s10107-011-0490-y, https://doi.org/10.1007/S10107-011-0490-Y doi:10.1007/S10107-011-0490-Y

2013 doi
[17]

Improving the parameter dependency for high-multiplicity scheduling on uniform machines

Klaus Jansen, Kai Kahler, Lis Pirotton, and Malte Tutas. Improving the parameter dependency for high-multiplicity scheduling on uniform machines. CoRR , abs/2409.04212, 2024. https://arxiv.org/abs/2409.04212 arXiv:2409.04212 , https://doi.org/10.48550/ARXIV.2409.04212 doi:10.4...

2024 doi
[18]

N ear-linear time algorithm for n-fold ILP s via color coding

Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. N ear-linear time algorithm for n-fold ILP s via color coding. SIAM J. Discret. Math. , 34(4):2282--2299, 2020. https://doi.org/10.1137/19M1303873 doi:10.1137/19M1303873

2020 doi
[19]

On integer programming and convolution

Klaus Jansen and Lars Rohwedder. On integer programming and convolution. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019 , volume 124 of LIPIcs , pages 43:1--43:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019. http...

2019 doi
[20]

On integer programming, discrepancy, and convolution

Klaus Jansen and Lars Rohwedder. On integer programming, discrepancy, and convolution. Math. Oper. Res. , 48(3):1481--1495, 2023. URL: https://doi.org/10.1287/moor.2022.1308, https://doi.org/10.1287/MOOR.2022.1308 doi:10.1287/MOOR.2022.1308

2023
[21]

Minkowski's convex body theorem and integer programming

Ravi Kannan. Minkowski's convex body theorem and integer programming. Math. Oper. Res. , 12(3):415--440, 1987. https://doi.org/10.1287/MOOR.12.3.415 doi:10.1287/MOOR.12.3.415

1987 doi
[22]

Scheduling meets n-fold integer programming

Dusan Knop and Martin Kouteck \' y . Scheduling meets n-fold integer programming. J. Sched. , 21(5):493--503, 2018. https://doi.org/10.1007/S10951-017-0550-0 doi:10.1007/S10951-017-0550-0

2018 doi
[23]

High-multiplicity n-fold IP via configuration LP

Dusan Knop, Martin Kouteck \' y , Asaf Levin, Matthias Mnich, and Shmuel Onn. High-multiplicity n-fold IP via configuration LP . Math. Program. , 200(1):199--227, 2023. https://doi.org/10.1007/S10107-022-01882-9 doi:10.1007/S10107-022-01882-9

2023 doi
[24]

Combinatorial n-fold integer programming and applications

Dusan Knop, Martin Kouteck \' y , and Matthias Mnich. Combinatorial n-fold integer programming and applications. Math. Program. , 184(1):1--34, 2020. https://doi.org/10.1007/S10107-019-01402-2 doi:10.1007/S10107-019-01402-2

2020 doi
[25]

Voting and bribing in single-exponential time

Dusan Knop, Martin Kouteck \' y , and Matthias Mnich. Voting and bribing in single-exponential time. ACM Trans. Economics and Comput. , 8(3):12:1--12:28, 2020. https://doi.org/10.1145/3396855 doi:10.1145/3396855

2020 doi
[26]

A parameterized strongly polynomial algorithm for block structured integer programs

Martin Kouteck \' y , Asaf Levin, and Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , volume 107 of LIPIcs , pages 85:1--85:14. Schloss Dagst...

2018 doi
[27]

Complexity results and exact algorithms for fair division of indivisible items: a survey

Trung Thanh Nguyen and J\" o rg Rothe. Complexity results and exact algorithms for fair division of indivisible items: a survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence , IJCAI '23, 2023. https://doi.org/10.24963/ijcai.2023...

2023 doi
[28]

Papadimitriou

Christos H. Papadimitriou. On the complexity of integer programming. J. ACM , 28(4):765--768, 1981. https://doi.org/10.1145/322276.322287 doi:10.1145/322276.322287

1981
[29]

Eth-tight FPT algorithm for makespan minimization on uniform machines

Lars Rohwedder. Eth-tight FPT algorithm for makespan minimization on uniform machines. CoRR , abs/2501.04859, 2025. https://arxiv.org/abs/2501.04859 arXiv:2501.04859 , https://doi.org/10.48550/ARXIV.2501.04859 doi:10.48550/ARXIV.2501.04859

2025 doi arXiv
[30]

Fine-grained equivalence for problems related to integer linear programming

Lars Rohwedder and Karol Wegrzycki. Fine-grained equivalence for problems related to integer linear programming. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 , volume 325 of LIPIcs , pages 83:1--83:18. Schloss Dagstuhl - Leibniz...

2025 doi
[31]

on some geometric methods in scheduling theory: A survey

Sergey Vasil'evich Sevast'janov. on some geometric methods in scheduling theory: A survey. Discret. Appl. Math. , 55(1):59--82, 1994. https://doi.org/10.1016/0166-218X(94)90036-1 doi:10.1016/0166-218X(94)90036-1

1994 doi
[32]

Bedingt konvergente reihen und konvexe systeme

Ernst Steinitz. Bedingt konvergente reihen und konvexe systeme. Journal für die reine und angewandte Mathematik , 1913(143):128--176, 1913. https://doi.org/doi:10.1515/crll.1913.143.128 doi:doi:10.1515/crll.1913.143.128

1913 doi

Pith tools

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

[1] [1]

Pitsoulis

Gautam Appa, Bal \' a zs Kotnyek, Konstantinos Papalamprou, and Leonidas S. Pitsoulis. Optimization with binet matrices. Oper. Res. Lett. , 35(3):345--352, 2007. https://doi.org/10.1016/J.ORL.2006.04.003 doi:10.1016/J.ORL.2006.04.003

work page doi:10.1016/j.orl.2006.04.003 2007

[2] [2]

A strongly polynomial algorithm for bimodular integer linear programming

Stephan Artmann, Robert Weismantel, and Rico Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 , pages 1206--1219. ACM , 2017. https://doi.org/10.1145/3055399.3055473 doi:10.1...

arXiv 2017

[3] [3]

On the Power of Linear Dependencies , pages 31--45

Imre B \'a r \'a ny. On the Power of Linear Dependencies , pages 31--45. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. https://doi.org/10.1007/978-3-540-85221-6_1 doi:10.1007/978-3-540-85221-6_1

work page doi:10.1007/978-3-540-85221-6_1 2008

[4] [4]

Woeginger

Robert Bredereck, Jiehua Chen, Sepp Hartung, Stefan Kratsch, Rolf Niedermeier, Ondrej Such \' y , and Gerhard J. Woeginger. A multivariate complexity analysis of lobbying in multiple referenda. J. Artif. Intell. Res. , 50:409--446, 2014. https://doi.org/10.1613/JAIR.4285 doi:10.1613/JAIR.4285

work page doi:10.1613/jair.4285 2014

[5] [5]

On complexity of lobbying in multiple referenda

Robin Christian, Mike Fellows, Frances Rosamond, and Arkadii Slinko. On complexity of lobbying in multiple referenda. Review of Economic Design , 11(3):217--224, Nov 2007. https://doi.org/10.1007/s10058-007-0028-1 doi:10.1007/s10058-007-0028-1

doi:10.1007/s10058-007-0028-1 2007

[6] [6]

Block-structured integer and linear programming in strongly polynomial and near linear time

Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschr \" o der, Lars Rohwedder, and Robert Weismantel. Block-structured integer and linear programming in strongly polynomial and near linear time. In D \' a niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pag...

work page doi:10.1137/1.9781611976465.101 2021

[7] [7]

Parameterized algorithms for block-structured integer programs with large entries

Jana Cslovjecsek, Martin Kouteck \' y , Alexandra Lassota, Michal Pilipczuk, and Adam Polak. Parameterized algorithms for block-structured integer programs with large entries. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 , pages 740--751. SIAM , 2024. https://doi.org/10.1137/1.9781611977912.29 ...

work page doi:10.1137/1.9781611977912.29 2024

[8] [8]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

doi:10.1007/978-3-319-21275-3 2015