Algorithms for Standard-form ILP Problems via Koml\'os' Discrepancy Setting
Pith reviewed 2026-05-10 16:31 UTC · model grok-4.3
The pith
Standard-form ILPs with k constraints solve in time O(κ_k)^{2k}Δ² for optimization and O(κ_k)^k Δ for feasibility via discrepancy DP.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The optimization problem can be solved in time O(κ_k)^{2k} Δ² and the feasibility problem in time O(κ_k)^k Δ, up to polynomial factors in the input size. Here κ_k denotes the maximum discrepancy over all matrices with k columns whose columns have Euclidean norm at most 1. The algorithms rely on a discrepancy-based dynamic programming procedure that exploits the full row rank of A together with the minor bound Δ.
What carries the argument
Discrepancy-based dynamic programming whose states are limited by the Komlós discrepancy constant κ_k to enumerate candidate solutions while respecting the minor bound Δ.
If this is right
- Feasibility is decided in O(κ_k)^k Δ time.
- Current κ_k bounds of roughly O(log^{1/4} k) yield O(log k)^{k/4 (1+o(1))} Δ for feasibility.
- The Komlós conjecture reduces both running times to 2^{O(k)} times polynomial factors in Δ and input size.
- The results apply to any full-rank matrix A whose k by k minors are bounded by Δ.
Where Pith is reading between the lines
- Any future improvement in algorithmic bounds for κ_k immediately yields faster ILP solvers without changing the rest of the framework.
- The same state-bounding technique may extend to other multi-constraint problems such as multidimensional knapsack.
- Empirical tests on random full-rank matrices with small k could check whether the discrepancy threshold is tight in practice.
- Links to lattice basis reduction might allow further pruning of the dynamic program states.
Load-bearing premise
The dynamic programming states bounded by the Komlós constant κ_k are guaranteed to include every feasible solution for any matrix A that has full row rank and maximum minor Δ.
What would settle it
An explicit ILP instance whose constraint matrix satisfies the minor bound Δ yet possesses a feasible solution whose partial sums exceed the discrepancy threshold κ_k, so that the dynamic program misses it.
read the original abstract
We study the standard-form ILP problem $\max\{ c^\top x \colon A x = b,\; x \in Z_{\geq 0}^n \}$, where $A\in Z^{k\times n}$ has full row rank. We obtain refined FPT algorithms parameterized by $k$ and $\Delta$, the maximum absolute value of a $k\times k$ minor of $A$. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Koml\'os' setting. Let $\kappa_k$ denote the maximum discrepancy over all matrices with $k$ columns whose columns have Euclidean norm at most $1$. Up to polynomial factors in the input size, the optimization problem can be solved in time $O(\kappa_k)^{2k}\Delta^2$, and the corresponding feasibility problem in time $O(\kappa_k)^k\Delta$. Using the best currently known bound $\kappa_k=\widetilde O(\log^{1/4}k)$, this yields running times $O(\log k)^{\frac{k}{2}(1+o(1))}\Delta^2$ and $O(\log k)^{\frac{k}{4}(1+o(1))}\Delta$, respectively. Under the Koml\'os conjecture, the dependence on $k$ in both running times reduces to $2^{O(k)}$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims refined FPT algorithms for standard-form ILP feasibility and optimization (max c^T x s.t. Ax=b, x>=0 integer) parameterized by k (number of constraints) and Δ (max |k x k minor| of A), where A has full row rank. The approach uses discrepancy-based dynamic programming in Komlós' setting, with running times O(κ_k)^{2k} Δ² for optimization and O(κ_k)^k Δ for feasibility (up to poly factors in input size), where κ_k is the max discrepancy for k-column matrices with Euclidean column norms <=1. This yields O(log k)^{k/2 (1+o(1))} Δ² and O(log k)^{k/4 (1+o(1))} Δ using current κ_k bounds, or 2^{O(k)} under the Komlós conjecture.
Significance. If verified, the results would give improved parameterized algorithms for ILP by integrating Komlós discrepancy bounds with DP, achieving better dependence on k than some prior FPT results for bounded-minor ILPs and reducing to single-exponential under the conjecture. The combination of discrepancy theory with DP for enumerating feasible solutions in this setting is a potentially useful technique.
major comments (3)
- [Dynamic Programming Construction] The central correctness claim for the discrepancy-based DP (that states bounded by κ_k suffice to capture all feasible solutions) requires explicit argument that every feasible x admits an ordering of its support with all prefix discrepancies <= κ_k. This must hold after scaling columns by the Δ-bounded minors, and the manuscript should show why the transition relation remains closed under this restriction without omitting solutions.
- [Komlós Setting and Scaling] The application of the Komlós bound κ_k (defined for unit-norm columns) to the (possibly non-unit-norm) column submatrices that arise in the DP after accounting for the minor bound Δ needs a detailed normalization or reduction step. Without it, the state space may grow beyond O(κ_k)^k by factors depending on Δ.
- [Matrix Assumptions and State Space] The full-row-rank assumption on A is invoked to eliminate extra residue classes, but the manuscript must concretely demonstrate how this prevents the DP state space from acquiring additional Δ-dependent factors in the exponent, as the bounded-minor condition alone may not suffice for the claimed bounds.
minor comments (2)
- Make the polynomial factors in the input size explicit in the running-time statements rather than leaving them implicit.
- Clarify the precise definition of κ_k in the context of the ILP matrix A and how it interacts with the non-negative integer constraint on x.
Simulated Author's Rebuttal
We thank the referee for the thorough review and for identifying points where the exposition of the discrepancy-based dynamic programming can be made more explicit. We address each major comment in turn and will revise the manuscript accordingly to strengthen the arguments without altering the claimed results.
read point-by-point responses
-
Referee: The central correctness claim for the discrepancy-based DP (that states bounded by κ_k suffice to capture all feasible solutions) requires explicit argument that every feasible x admits an ordering of its support with all prefix discrepancies <= κ_k. This must hold after scaling columns by the Δ-bounded minors, and the manuscript should show why the transition relation remains closed under this restriction without omitting solutions.
Authors: We agree that the manuscript would benefit from a self-contained lemma establishing the existence of a suitable ordering. In the revision we will insert a new lemma immediately preceding the DP description: for any feasible nonnegative integer solution x, there exists an ordering of the columns in its support such that every prefix sum, after scaling each column by the reciprocal of its Euclidean norm (which is controlled by the Δ-minor bound), has discrepancy at most κ_k. The proof proceeds by contradiction using the definition of κ_k and the fact that any violating ordering can be rearranged via a greedy swap argument that preserves feasibility. We will also verify that the transition function of the DP, which only adds a single column when the resulting partial sum stays inside the κ_k-bounded box, is closed under this ordering and therefore enumerates every feasible solution exactly once up to the polynomial overhead already stated. revision: yes
-
Referee: The application of the Komlós bound κ_k (defined for unit-norm columns) to the (possibly non-unit-norm) column submatrices that arise in the DP after accounting for the minor bound Δ needs a detailed normalization or reduction step. Without it, the state space may grow beyond O(κ_k)^k by factors depending on Δ.
Authors: The current write-up treats normalization implicitly when invoking the Komlós constant. We will add an explicit normalization paragraph in the DP construction section: each column a_j appearing in a partial solution is replaced by a_j / ||a_j||_2 (with the Euclidean norm bounded via the Δ-minor hypothesis), the target right-hand side is scaled commensurately, and the discrepancy bound κ_k is applied to the unit-norm vectors. Because the scaling factor is absorbed into the already-present polynomial dependence on Δ, the number of reachable states remains O(κ_k)^k; the extra Δ factor appears only in the time per transition, preserving the overall O(κ_k)^k Δ bound for feasibility. revision: yes
-
Referee: The full-row-rank assumption on A is invoked to eliminate extra residue classes, but the manuscript must concretely demonstrate how this prevents the DP state space from acquiring additional Δ-dependent factors in the exponent, as the bounded-minor condition alone may not suffice for the claimed bounds.
Authors: We will expand the preliminaries to include a short calculation showing that full row rank together with the Δ-minor bound implies that the lattice generated by the columns of A has determinant at most Δ^k and that Ax = b lies in a single coset of this lattice. Consequently, the DP only needs to track the partial sum inside a fundamental domain whose volume is bounded by a function of Δ alone; when intersected with the κ_k-box the total number of integer points remains O(κ_k)^k times a polynomial in Δ, with no additional exponential dependence on Δ in the exponent. A concrete one-paragraph derivation using the Hadamard inequality on the minors will be supplied. revision: yes
Circularity Check
No circularity; running times derived from external Komlós bound via DP state-space analysis
full rationale
The derivation proceeds by constructing a discrepancy-based dynamic program whose state space is bounded using the externally defined Komlós constant κ_k (maximum discrepancy for k-column matrices with column Euclidean norms ≤1). The running times O(κ_k)^{2k}Δ² (optimization) and O(κ_k)^k Δ (feasibility) follow directly from enumerating states of size (O(κ_k))^k, multiplied by polynomial factors in Δ arising from the minor bound and full-row-rank assumption on A. Because κ_k and its known bounds (e.g., Õ(log^{1/4} k)) are imported from prior discrepancy literature rather than fitted or redefined inside the paper, and no internal parameter is optimized against the target running time, the chain contains no self-definitional, fitted-input, or self-citation reductions. The full-row-rank and Δ-minor assumptions serve only to bound the number of residue classes and ensure DP transitions remain closed, without collapsing the claimed complexity back onto the inputs by construction.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Properties of the Komlós discrepancy constant κ_k and matrix discrepancy bounds hold as stated in prior literature.
- domain assumption Dynamic programming over discrepancy states correctly enumerates all non-negative integer solutions to Ax = b when the state space is bounded by κ_k.
Reference graph
Works this paper leans on
-
[1]
Noga Alon and Joel H Spencer. The probabilistic method . John Wiley & Sons, 2016
work page 2016
-
[2]
Balancing vectors and gaussian measures of n-dimensional convex bodies
Wojciech Banaszczyk. Balancing vectors and gaussian measures of n-dimensional convex bodies. Random Structures & Algorithms , 12(4):351--360, 1998
work page 1998
-
[3]
Nikhil Bansal and Haotian Jiang. Decoupling via affine spectral-independence: Beck-Fiala and Koml\'os bounds beyond Banaszczyk . arXiv preprint arXiv:2508.03961 , 2025
-
[4]
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Karl Bringmann, Nick Fischer, and Vasileios Nakos. Deterministic and las vegas algorithms for sparse nonnegative convolution. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms ( SODA 2022) , pages 3069--3090. SIAM, 2022. https://doi.org/10.1137/1.9781611977073.119 doi:10.1137/1.9781611977073.119
-
[5]
Delta-modular ILP problems of bounded co-dimension, discrepancy, and convolution
M Cherniavskii, D Gribanov, D Malyshev, and Panos M Pardalos. Delta-modular ILP problems of bounded co-dimension, discrepancy, and convolution. arXiv preprint arXiv:2405.17001 , 2024
-
[6]
Proximity Results and Faster Algorithms for Integer Programming Using the S teinitz Lemma
Friedrich Eisenbrand and Robert Weismantel. Proximity Results and Faster Algorithms for Integer Programming Using the S teinitz Lemma . ACM Transactions on Algorithms , 16(1), nov 2019. https://doi.org/10.1145/3340322 doi:10.1145/3340322
-
[7]
Essentially optimal sparse polynomial multiplication
Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray. Essentially optimal sparse polynomial multiplication. In Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation , pages 202--209, 2020
work page 2020
-
[8]
V. Gribanov, D., A. Shumilov, I., S. Malyshev, D., and M. Pardalos, P. On -modular integer linear problems in the canonical form and equivalent problems. J Glob Optim , 2022. https://doi.org/10.1007/s10898-022-01165-9 doi:10.1007/s10898-022-01165-9
-
[9]
The ellipsoid method and its consequences in combinatorial optimization
Martin Gr \"o tschel, L \'a szl \'o Lov \'a sz, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica , 1(2):169--197, 1981
work page 1981
-
[10]
On integer programming, discrepancy, and convolution
K. Jansen and L. Rohwedder. On integer programming, discrepancy, and convolution. Mathematics of Operations Research , 2022. https://doi.org/10.1287/moor.2022.1308 doi:10.1287/moor.2022.1308
-
[11]
Randomized rounding for the largest simplex problem
Aleksandar Nikolov. Randomized rounding for the largest simplex problem. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 861--870, 2015
work page 2015
-
[12]
Christos H. Papadimitriou. On the complexity of integer programming. J. ACM , 28(4):765--768, October 1981. https://doi.org/10.1145/322276.322287 doi:10.1145/322276.322287
- [13]
-
[14]
Algorithms for matrix canonical forms
Arne Storjohann. Algorithms for matrix canonical forms . PhD thesis, ETH Zurich, 2000
work page 2000
-
[15]
Asymptotically fast computation of H ermite normal forms of integer matrices
Arne Storjohann and George Labahn. Asymptotically fast computation of H ermite normal forms of integer matrices. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation , ISSAC '96, pages 259--266, New York, NY, USA, 1996. Association for Computing Machinery. https://doi.org/10.1145/236869.237083 doi:10.1145/236869.237083
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.