Convex Minimization with Integer Minima in Õ(n4) Time

Given a convex function f on R n with an integer minimizer, we show how to find an exact minimizer of f using O(n 2 log n) calls to a separation oracle and O(n 4 log n) time. The previous best polynomial time algorithm for this problem given in [Jiang, SODA 2021, JACM 2022] achieves O(n 2 log log n/ log n) oracle complexity. However, the overall runtime of Jiang's algorithm is at least Ω(n 8 ), due to expensive sub-routines such as the Lenstra-Lenstra-Lovász (LLL) algorithm [Lenstra, Lenstra, Lovász, Math. Ann. 1982] and random walk based cutting plane method [Bertsimas, Vempala, JACM 2004]. Our significant speedup is obtained by a nontrivial combination of a faster version of the LLL algorithm due to [Neumaier, Stehlé, ISSAC 2016] that gives similar guarantees, the volumetric center cutting plane method (CPM) by [Vaidya, FOCS 1989] and its fast implementation given in [Jiang, Lee, Song, Wong, STOC 2020].

For the special case of submodular function minimization (SFM), our result implies a strongly polynomial time algorithm for this problem using O(n 3 log n) calls to an evaluation oracle and O(n 4 log n) additional arithmetic operations. Both the oracle complexity and the number of arithmetic operations of our more general algorithm are better than the previous best-known runtime algorithms for this specific problem given in [