Convex Minimization with Integer Minima in O(n^4) Time - Jiang, Haotian; Lee, Yin Tat; Song, Zhao; Zhang, Lichen (SODA 2024, 2024)
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 n) calls to a separation oracle and O(n^4 n) time. The previous best polynomial time algorithm for this problem given in [Jiang, SODA 2021, JACM 2022] achieves O(n^2n/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 n) calls to an evaluation oracle and O(n^4 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 [Lee, Sidford, Wong, FOCS 2015] and [Dadush, Végh, Zambelli, SODA 2018, MOR 2021].