Totally $\Delta$-modular IPs with two non-zeros in most rows

Stefan Kober

REVIEW 2 major objections 3 minor 28 references

Totally $\Delta$-modular IPs with two non-zeros in most rows

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read For fixed Δ and k, this paper provides a strongly polynomial-time algorithm for integer programs whose totally Δ-modular constraint matrix has at most two non-zeros per row after deleting at most k rows and columns.

desk verdict Real extension of the two-nonzeros-per-row IP result with a nice signed-graph decomposition, but the strong-polynomiality claim rests on an unproven black-box transfer. read the letter →

arxiv 2411.15282 v2 pith:3NKFR37O submitted 2024-11-22 cs.DS cs.DMmath.COmath.OC

Stefan Kober This is my paper · ORCID

classification cs.DScs.DMmath.COmath.OC MSC 90C1090C2705C8568Q25

keywords integerprogrammingtotallyΔ-modularmatricesboundedsubdeterminantstwonon-zerosperrowtree-decompositiondynamicpartiallyorderedknapsackparameterizedcomplexity

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

Integer programs with bounded subdeterminants are conjectured to be solvable in polynomial time, and this paper proves a new case of that conjecture. Fix Δ and k; if the constraint matrix is totally Δ-modular (every subdeterminant has absolute value at most Δ) and has at most two non-zeros per row after deleting at most k rows and columns, then the IP can be solved in strongly polynomial time. The result extends the known polynomial-time treatment of the two-nonzero case by allowing additional unifying constraints and variables. The proof reduces the general instance to a central problem with k extra rows, translates the subdeterminant bound into a graph-theoretic decomposition, and solves the pieces with a dynamic program. Two fixed-parameter-tractable corollaries follow, including an FPT algorithm for the k-dimensional partially ordered knapsack problem.

What carries the argument

The central object is the alternating weight of a tree: for a signed graph S with vertex weights w, a tree T has bipartition X_T,Y_T such that even edges stay inside a part and odd edges cross, and alt(T,w) = |Σ_{v∈X_T}w(v) − Σ_{v∈Y_T}w(v)|; alt(S,w) is the maximum over all trees. Proposition 11 shows that this quantity is always a subdeterminant of [A; w^T], hence bounded by Δ. Lemma 12 then shows that a graph containing an r-decorated tree — a tree with at least r terminal leaves — forces some weight function to have alternating weight at least r/(2k), so bounded subdeterminants forbid such trees. That absence is exactly what a graph-decomposition lemma (Theorem 13) needs to hand the paper a star-decomposition with a bounded number of terminals at the center, which the paper refines into the type-(i)/(ii) tree-decomposition of Theorem 16 that the dynamic program runs on.

What would settle it

A direct test: find a fixed-Δ, two-nonzero-per-row IP whose only algorithms require a number of arithmetic operations that grows with the bit length of the entries; because such IPs are exactly the type-(ii) leaf subproblems, the dynamic program could not be strongly polynomial unless that base case is. Concretely, checking whether Theorem 1 can be strengthened to strongly polynomial, or finding a lower bound showing it cannot, would settle Theorem 4 as stated.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 4: for fixed constants Δ and k, every instance of Problem 2 — an integer program whose totally Δ-modular matrix has at most two non-zeros per row after removing at most k rows and columns — is solvable in strongly polynomial time. The argument works by a polynomial reduction to Problem 3, where the only messy part is a matrix with two non-zeros per row plus k extra rows; there, the bound on subdeterminants is shown to imply a structural restriction on an associated signed graph. Proposition 11 identifies the alternating weight of a tree as a subdeterminant, Lemma 12 turns bounded alternating weight into the absence of large decorated trees, and Theorem 16 converts that absence into a tree-decomposition with bounded adhesion and degree in which every leaf bag's terminals reappear in its parent. A bottom-up dynamic program on this decomposition solves the instance, with leaf bags handled either by bounded enumeration or by the black-box two-nonzero base case of Theorem 1.

Load-bearing premise

The claim of strong polynomiality is supported only if the black-box algorithm for the two-nonzero base case (Theorem 1) is itself strongly polynomial for fixed Δ, yet the paper states that theorem as merely polynomial-time.

Editorial extensions

If this is right

For fixed Δ and k, the algorithmic boundary of bounded-subdeterminant IPs now includes all matrices that become two-nonzero per row after deleting at most k rows and columns.
The reduction to Problem 3 means the proximity theorem of Cook et al. is used directly, avoiding auxiliary proximity or solution-decomposition results needed elsewhere.
When the matrix is totally unimodular, Corollary 5 gives an FPT algorithm for Problem 3 parameterized by the largest subdeterminant, using a dimension-free proximity bound.
Corollary 6 gives an FPT algorithm for the k-dimensional partially ordered knapsack problem, parameterized by the maximum total weight of a connected subgraph, a case for which few polynomial results were known.
The structural decomposition theorem (Theorem 16) shows that the hard almost-embeddable bags of the cographic case are never needed for two-nonzero-plus-k matrices.

Reading between the lines

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

If the base case of Theorem 1 is only weakly polynomial, the paper's main theorem still holds as a polynomial-time statement but not as a strongly polynomial one; the gap is local, not in the decomposition.
The alternating-weight invariant could serve as a certificate for bounded subdeterminants in other matrix families: any graph with a tree whose alternating weight exceeds a known bound cannot be the signed graph of a totally Δ-modular matrix.
The sharp contrast with the cographic near-totally-unimodular setting — where almost-embeddable bags are necessary — suggests testing whether allowing both almost-embeddable bags and two-nonzero structure yields a still larger tractable class.
A concrete computational test: generate random totally Δ-modular instances with fixed Δ,k and growing coefficient sizes; if the observed runtime grows with bit length, suspect the missing strongly-polynomial base case.

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.

Desk Editor's Note

read the letter

Quick take: the paper has a real new theorem—extending the Fiorini–Joret–Weltge–Yuditsky two-nonzeros-per-row algorithm to allow a constant number of extra rows and columns—and the signed-graph machinery it introduces is worth reading. The structural results in Sections 4 and 5 are clean, especially the alternating-weight invariant in Proposition 11 and the decorated-tree bound in Lemma 12. Avoiding the graph minor structure theorem is a genuine plus; Theorem 16's decomposition is built from elementary tools and appears correct. I also see no circular reasoning: the subdeterminant bounds are assumptions, not conclusions, and the citation to the author's thesis for Corollary 5 is fine.

The soft spot is the strong-polynomiality claim. The proof of Theorem 4 solves type-(ii) bags by invoking Theorem 1 as a black box after fixing terminal variables. But Theorem 1 is stated only as polynomial-time. Strong polynomiality of the whole DP requires that the local solver for bounded subdeterminants and two nonzeros per row runs in time polynomial in n (with Δ fixed) and independent of the bit lengths of b and c. No argument in the paper establishes that; it may be true, but it is not shown. The reduction in Proposition 8 also recenters around an LP relaxation, and again no strongly polynomial LP solver is identified for the matrix class with extra rows. So the main theorem, as written, is not fully supported. If the claim were weakened to polynomial-time, the paper would be on solid ground and the contribution would still be new. Also, the DP correctness proof is terse—the induction in Section 6 is more of a sketch than a full argument, and the 'all optimal solutions decompose' step deserves a careful proof.

None of this is a takedown. The structural core is sound and the techniques should be useful. A serious referee could resolve the complexity gap by either strengthening Theorem 1 (or its known running time) or adjusting the theorem statement. The paper deserves peer review; I would not desk-reject it. It is aimed at the bounded-subdeterminant IP community and researchers working on FPT for knapsack-like problems. I'd bring it to a seminar and cite the alternating-weight lemma.

Referee Report

2 major / 3 minor

Summary. The paper studies integer programs of the form min{c^T x : M x ≤ b, x ∈ Z^n} for totally Δ-modular matrices M that have at most two non-zeros per row after deleting at most k rows and columns, for fixed Δ and k (Problem 2). The main theorem, Theorem 4, claims a strongly polynomial-time algorithm for this class. The proof reduces Problem 2 to Problem 3, where a {0, ±1} matrix A with two non-zeros per row is augmented by k arbitrary rows W. The paper represents A via a signed graph, introduces the alternating weight of a tree, shows that bounded subdeterminants imply the absence of large decorated trees, applies a tree-decomposition theorem of Ding, and then uses a bottom-up dynamic program over the decomposition. Corollaries give an FPT algorithm for Problem 3 when A is totally unimodular and an FPT algorithm for the k-dimensional partially ordered knapsack problem.

Significance. If the main claim is correct, this is a meaningful extension of the tractability boundary for IPs with bounded subdeterminants, going beyond the two-nonzeros-per-row case of Fiorini et al. and the cographic nearly-totally-unimodular case of Aprile et al. The structural analysis is largely self-contained: the alternating-weight bound in Proposition 11, the decorated-tree obstruction in Lemma 12, and the tree-decomposition in Theorem 16 are clear and seem correct. The dynamic program is also reasonably explicit. However, the advertised strongly polynomial complexity is not supported by the written proof. Theorem 1, the main black box, is stated only as polynomial-time, and the reduction in Proposition 8 uses an LP relaxation solution without a strong-polynomiality argument. As written, the proof supports at most a polynomial-time algorithm under the stated black boxes. This gap affects the central claim of the paper.

major comments (2)

[Section 6, proof of Theorem 4, runtime paragraph] The proof states that each local instance can be solved in polynomial time and that for bags of type (ii) this is done by invoking Theorem 1, which the manuscript states as a polynomial-time algorithm. Polynomial time does not imply strongly polynomial time; if the Fiorini-Joret-Weltge-Yuditsky algorithm depends on log ||b||, log ||c||, or uses an integer-programming oracle, the overall DP is only weakly polynomial. Since Theorem 4 explicitly claims a strongly polynomial-time algorithm, the proof must either give a strongly polynomial version of the type-(ii) solver or the theorem must be weakened to polynomial time. This is the central load-bearing step of the paper.
[Section 3, Proposition 8 and its proof] The reduction from Problem 2 to Problem 3 uses an optimal solution x* of the LP relaxation to recenter the variables and then solves a polynomial number of Problem 3 instances. No strongly polynomial algorithm is identified for solving that LP relaxation for the class in Problem 2, and the extra rows W may have many non-zeros per row. Moreover, Proposition 8 is itself stated only as a polynomial-time reduction. Therefore, even a strongly polynomial algorithm for Problem 3 would not automatically imply Theorem 4 without an additional argument. The proof of Theorem 4 says 'by Proposition 8 it suffices to give a polynomial-time algorithm for Problem 3,' which confirms that the written argument establishes at most polynomial time, not strong polynomiality.

minor comments (3)

[Section 6] The state-count expression '(2n∆f7(n,∆)+1)^k · (2f7(n,∆)+1)^{O((k∆)^2)}' is polynomial in n for fixed ∆ and k, but the paper should say this explicitly and state the arithmetic model, since the distinction between polynomial and strongly polynomial time is central to the main theorem.
[Section 5, proof of Theorem 16] The treatment of disconnected graphs is quite compressed: the reader must infer how the bags of the component decompositions are combined with the empty bags at the c_i nodes. A short explicit construction of the bags for the comb attachments would improve readability.
[References] Reference [12] contains a corrupted author name ('W˛egrzycki'), and the paper uses both 'parametrized' and 'parameterized'; these should be normalized.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is supported by independent structural derivations and an external black-box algorithm.

full rationale

The derivation is self-contained for the structural part. Proposition 11 proves that the alternating weight of any tree is bounded by a subdeterminant of the combined matrix, using an explicit induction on the tree and elementary row operations. Given this bound, Lemma 12 shows that an r-decorated tree would force alternating weight at least r/(2k), so the condition that G has no (2k*Delta+1)-decorated tree follows from the total Delta-modularity assumption; it is not imposed by hand. Theorem 16 converts Ding's star-decomposition into the required bounded-adhesion tree-decomposition without assuming the conclusion. The dynamic program in Section 6 solves each local instance either by enumeration inside a bounded bag or by invoking Theorem 1, which is an external prior algorithm for exactly the same class of integer programs with two non-zeros per row and bounded subdeterminants. The self-citations to the author's thesis and to the coauthored SODA paper are used only for corollaries and not as the load-bearing premise of Theorem 4. The only substantive concern is that Theorem 4 claims strong polynomiality but the proof states only that base-case instances are solved in polynomial time; this is a running-time gap, not circularity.

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

No fitted parameters appear; Δ and k are fixed problem parameters, not values fit to data. The only new object, the alternating weight of a tree, is a graph invariant introduced by definition, not a postulated entity requiring independent evidence. All other load-bearing background results are cited external theorems.

assumptions (5)

standard math Cook, Gerards, Schrijver and Tardos proximity bound: for a totally Δ-modular IP there is an optimal integer solution within f7(n,Δ) of an LP optimum.
Invoked in Section 3 to recenter around an LP solution and to bound all variable ranges by f7(n,Δ).
standard math Every {0,±1} matrix with at most two non-zeros per row is the edge-vertex incidence matrix of a signed graph.
Section 4 uses this identification to convert the constraint matrix A into a signed graph and to transfer subdeterminant bounds to alternating weights.
standard math Ding's structural lemma, Theorem 13: graphs with no r-decorated tree admit the described star-decomposition with O(r^2) center-terminal bound.
Theorem 13 is cited from [11] and is the geometric engine behind Theorem 16; all steps are claimed constructive.
domain assumption Fiorini, Joret, Weltge and Yuditsky, Theorem 1: polynomial-time algorithm for IPs that are totally Δ-modular and have at most two non-zeros per row.
Used as black box for local type-(ii) bags; the main theorem assumes this algorithm exists with the stated polynomial guarantee.
standard math Fiorini et al. Lemma 4: in the relevant matrices only O(log Δ) columns have entries exceeding 1 in absolute value.
Used in the reduction from Problem 2 to Problem 3 to enumerate assignments to large-entry columns.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Totally $\Delta$-modular IPs with two non-zeros in most rows." pith.science (2026). https://pith.science/paper/3NKFR37O

@misc{pith2026241115282,
  author       = {Pith},
  title        = {Pith review of: Totally $\Delta$-modular IPs with two non-zeros in most rows},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3NKFR37O}},
  note         = {Machine review of arXiv:2411.15282}
}

read the original abstract

Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge \& Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables.

Figures

Figures reproduced from arXiv: 2411.15282 by the authors.

**Figure 1.** Recent results on IPs with bounded subdeterminants: bimodular matrices [3], {a,b,c}- modular matrices [17], two non-zeros per row (2 non-zeros) [16], nearly totally unimodular matrices, the cographic case (cographic +k) [2], and this work (2 non-zeros +k, shaded in green). Secondly, we work on IPs over a class of constraint matrices with a constant number of extra rows. Such problems appear naturally within combina… view at source ↗

**Figure 2.** A depiction of the structure of graphs in Lemma 15. The red vertices are terminals. The collections of components Ki (dashed) and L j (dotted) are used in the proof of Theorem 16. Theorem 16. Let r ∈ N and G be a graph with set of terminals R. There is a function f16(r ) ∈ O(r 2 ) with the following properties. If G has no r -decorated tree as a subgraph, then there is a tree-decomposition (T,B) of G with adhesion-s… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

Mathe- matical Programming 182(1), 175–198 (2020)

Aliev, I., Henk, M., Oertel, T .: Distances to lattice points in knapsack polyhedra. Mathe- matical Programming 182(1), 175–198 (2020)

work page 2020
[2]

ACM-SIAM Sym- posium on Discrete Algorithms (SODA25) (2025)

Aprile, M., Fiorini, S., Joret, G., Kober, S., Seweryn, M.T ., Weltge, S., Yuditsky, Y.: Integer programs with nearly totally unimodular matrices: the cographic case. ACM-SIAM Sym- posium on Discrete Algorithms (SODA25) (2025)

work page 2025
[3]

In: Proceedings of the 49th Annual ACM SIGACT Sympo- sium on Theory of Computing

Artmann, S., Weismantel, R., Zenklusen, R.: A strongly polynomial algorithm for bimodu- lar integer linear programming. In: Proceedings of the 49th Annual ACM SIGACT Sympo- sium on Theory of Computing. pp. 1206–1219 (2017) Totally ∆-modular IPs with two non-zeros in most rows 15

work page 2017
[4]

Mathematical Programming pp

Averkov, G., Schymura, M.: On the maximal number of columns of a ∆-modular integer matrix: bounds and computations. Mathematical Programming pp. 1–29 (2023)

work page 2023
[5]

Mathematics of Operations Research (2023)

Celaya, M., Kuhlmann, S., Paat, J., Weismantel, R.: Proximity and flatness bounds for linear integer optimization. Mathematics of Operations Research (2023)

work page 2023
[6]

In: International Conference on Integer Programming and Combinatorial Optimization

Celaya, M., Kuhlmann, S., Weismantel, R.: On matrices over a polynomial ring with restricted subdeterminants. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 43–56. Springer (2024)

work page 2024
[7]

Mathematical Programming 34(3), 251–264 (1986)

Cook, W ., Gerards, A.M., Schrijver, A., Tardos, É.: Sensitivity theorems in integer linear pro- gramming. Mathematical Programming 34(3), 251–264 (1986)

work page 1986
[8]

In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

Dadush, D., Koh, Z.K., Natura, B., Olver, N., Végh, L.A.: A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. pp. 1561–1572 (2024)

work page 2024

Show all 28 references

[9]

Master’ s thesis, Simon Fraser University (2020)

Dhahan, J.: The maximum weight stable set problem with a budget constraint. Master’ s thesis, Simon Fraser University (2020)

2020
[10]

Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg; New York, fourth edn. (2010)

2010
[11]

arXiv:1702.01355 (2017)

Ding, G.: Graphs without large K2,n-minors. arXiv:1702.01355 (2017)

2017 arXiv
[12]

In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)

Eisenbrand, F ., Rohwedder, L., W˛ egrzycki, K.: Sensitivity, proximity and FPT algorithms for exact matroid problems. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). pp. 1610–1620. IEEE (2024)

2024
[13]

ACM Transactions on Algorithms (TALG)16(1), 1–14 (2019)

Eisenbrand, F ., Weismantel, R.: Proximity results and faster algorithms for integer pro- gramming using the Steinitz lemma. ACM Transactions on Algorithms (TALG)16(1), 1–14 (2019)

2019
[14]

Surveys in Combinatorics pp

Ekbatani, F ., Natura, B., Végh, L.A.: Circuit imbalance measures and linear programming. Surveys in Combinatorics pp. 64–114 (2022)

2022
[15]

In: International Symposium on Combinatorial Optimization

Ferrarini, L., Fiorini, S., Kober, S., Yuditsky, Y.: Total matching and subdeterminants. In: International Symposium on Combinatorial Optimization. pp. 192–204. Springer (2024)

2024
[16]

Journal of the ACM72(1), 1–50 (2025)

Fiorini, S., Joret, G., Weltge, S., Yuditsky, Y.: Integer programs with bounded subdetermi- nants and two nonzeros per row. Journal of the ACM72(1), 1–50 (2025)

2025
[17]

Vietnam Journal of Mathematics 50(2), 469–485 (2022)

Glanzer, C., Stallknecht, I., Weismantel, R.: Notes on {a, b, c}-modular matrices. Vietnam Journal of Mathematics 50(2), 469–485 (2022)

2022
[18]

Linear Algebra and its Applications 218, 213–224 (1995)

Grossman, J.W ., Kulkarni, D.M., Schochetman, I.E.: On the minors of an incidence matrix and its Smith normal form. Linear Algebra and its Applications 218, 213–224 (1995)

1995
[19]

Mathematics of Operations Research 8(1), 1–14 (1983)

Johnson, D.S., Niemi, K.: On knapsacks, partitions, and a new dynamic programming technique for trees. Mathematics of Operations Research 8(1), 1–14 (1983)

1983
[20]

Kober, S.A.: Three perspectives on integer programming: practical and theoretical appli- cations, and the case of bounded subdeterminants. Ph.D. thesis, Technische Universität München (2023)

2023
[21]

Discrete Applied Mathematics 155(8), 889–897 (2007)

Kolliopoulos, S.G., Steiner, G.: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155(8), 889–897 (2007)

2007
[22]

Mathematics of Operations Research (2022)

Lee, J., Paat, J., Stallknecht, I., Xu, L.: Polynomial upper bounds on the number of differing columns of ∆-modular integer programs. Mathematics of Operations Research (2022)

2022
[23]

In: International Conference on Integer Programming and Combinatorial Optimization

Liu, S., Xu, C.: On the congruency-constrained matroid base. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 280–293. Springer (2024)

2024
[24]

Mathematical Programming pp

Nägele, M., Nöbel, C., Santiago, R., Zenklusen, R.: Advances on strictly ∆-modular IPs. Mathematical Programming pp. 1–30 (2024)

2024
[25]

Mathematics of Operations Research 49(3), 1303–1348 (2024)

Nägele, M., Santiago, R., Zenklusen, R.: Congruency-constrained TU problems beyond the bimodular case. Mathematics of Operations Research 49(3), 1303–1348 (2024)

2024
[26]

Journal of the ACM (JACM) 29(2), 285–309 (1982) 16 S

Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree prob- lems. Journal of the ACM (JACM) 29(2), 285–309 (1982) 16 S. Kober

1982
[27]

American Mathematical Soc

Shevchenko, V .: Qualitative topics in integer linear programming. American Mathematical Soc. (1996), original manuscript in russian

1996
[28]

Op- erations Research 34(2), 250–256 (1986)

Tardos, É.: A strongly polynomial algorithm to solve combinatorial linear programs. Op- erations Research 34(2), 250–256 (1986)

1986

Pith tools

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

[1] [1]

Mathe- matical Programming 182(1), 175–198 (2020)

Aliev, I., Henk, M., Oertel, T .: Distances to lattice points in knapsack polyhedra. Mathe- matical Programming 182(1), 175–198 (2020)

work page 2020

[2] [2]

ACM-SIAM Sym- posium on Discrete Algorithms (SODA25) (2025)

Aprile, M., Fiorini, S., Joret, G., Kober, S., Seweryn, M.T ., Weltge, S., Yuditsky, Y.: Integer programs with nearly totally unimodular matrices: the cographic case. ACM-SIAM Sym- posium on Discrete Algorithms (SODA25) (2025)

work page 2025

[3] [3]

In: Proceedings of the 49th Annual ACM SIGACT Sympo- sium on Theory of Computing

Artmann, S., Weismantel, R., Zenklusen, R.: A strongly polynomial algorithm for bimodu- lar integer linear programming. In: Proceedings of the 49th Annual ACM SIGACT Sympo- sium on Theory of Computing. pp. 1206–1219 (2017) Totally ∆-modular IPs with two non-zeros in most rows 15

work page 2017

[4] [4]

Mathematical Programming pp

Averkov, G., Schymura, M.: On the maximal number of columns of a ∆-modular integer matrix: bounds and computations. Mathematical Programming pp. 1–29 (2023)

work page 2023

[5] [5]

Mathematics of Operations Research (2023)

Celaya, M., Kuhlmann, S., Paat, J., Weismantel, R.: Proximity and flatness bounds for linear integer optimization. Mathematics of Operations Research (2023)

work page 2023

[6] [6]

In: International Conference on Integer Programming and Combinatorial Optimization

Celaya, M., Kuhlmann, S., Weismantel, R.: On matrices over a polynomial ring with restricted subdeterminants. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 43–56. Springer (2024)

work page 2024

[7] [7]

Mathematical Programming 34(3), 251–264 (1986)

Cook, W ., Gerards, A.M., Schrijver, A., Tardos, É.: Sensitivity theorems in integer linear pro- gramming. Mathematical Programming 34(3), 251–264 (1986)

work page 1986

[8] [8]

In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

Dadush, D., Koh, Z.K., Natura, B., Olver, N., Végh, L.A.: A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. pp. 1561–1572 (2024)

work page 2024