arXiv:2303.14605math.OC
The Subspace Flatness Conjecture and Faster Integer Programming
Abstract
In a seminal paper, Kannan and Lovász (1988) considered a quantity $μ_{KL}(Λ,K)$ which denotes the best volume-based lower bound on the covering radius $μ(Λ,K)$ of a convex body $K$ with respect to a lattice $Λ$. Kannan and Lovász proved that $μ(Λ,K) \leq n \cdot μ_{KL}(Λ,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log(2n))$ factor suffices, which would match the lower bound from the work of Kannan and Lovász. We settle this conjecture up to a constant in the exponent by proving that $μ(Λ,K) \leq O(\log^{3}(2n)) \cdot μ_{KL} (Λ,K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a $(\log(2n))^{O(n)}$-time randomized algorithm to solve integer programs in $n$ variables. Another implication of our main result is a near-optimal flatness constant of $O(n \log^{2}(2n))$, improving on the previous bound of $O(n^{4/3} \log^{O(1)} (2n))$.
Great short article. I haven't looked deeply into the math behind this yet, but this looks to be a preprint [0]. It doesn't appear they're looking directly at the Space Groups as a way to reduce out any symmetries or repetitions that may occur (thus generalizing simplifications…
DuanemclemoreView on HNParent context
[2023] The paper was uploaded first in March https://arxiv.org/abs/2303.14605
genmanView on HNParent context
It seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605 I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?
andrewp123View on HNParent context
The randomized algorithm that Reis & Rothvoss [1] present at the end of their paper will not be implemented in Gurobi/CPLEX/XPRESS. It remains a fantastic result regardless (see below). But first let me explain. In terms of theoretical computational complexity, the best…
xkcd386View on HNParent context
The original paper (https://arxiv.org/pdf/2303.14605.pdf) that the linked article reports on is a theoretical algorithms paper, and does not contain any references to actual solvers or implementations. For practical cases it is not that important what the worst-case complexity…
mzlView on HNParent context
The abstract is more informative: https://arxiv.org/abs/2303.14605 We obtain a (log(2n))^O(n)-time randomized algorithm to solve integer programs in n variables. So the work is theoretical: a better exponential-time algorithm than the previous best, based on some analysis of the…
j2kunView on HNParent context