Convex Minimization with Integer Minima in Õ(n4) Time
Convex Minimization with Integer Minima in Õ(n4) Time
复制标题
Õ(n4) 时间内的整数极小值凸最小化
DOI：
10.48550/arxiv.2304.03426
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Licheng Zhang
中科院分区：
文献类型：
--
作者：
Hao Jiang;Y. Lee;Zhao Song;Licheng Zhang
给定$\mathbb{R}^n$上的一个凸函数$f$和一个整数最小化器，我们将展示如何使用$O(n^2 \log n)$调用分离oracle和$O(n^4 \log n)$时间来找到$f$的精确最小化器。先前给出的针对该问题的最佳多项式时间算法[Jiang， SODA 2021， JACM 2022]实现了$O(n^2\log\log n/\log n)$ oracle复杂度。然而，Jiang的算法的总体运行时间至少是$\widetilde{\Omega}(n^8)$，因为有昂贵的子例程，如Lenstra-Lenstra-Lovász （LLL）算法[Lenstra， Lenstra, Lovász, Math]。Ann. 1982]和基于随机游动的切割平面方法[Bertsimas， Vempala, JACM 2004]。我们的显著加速是通过将提供类似保证的[Neumaier， stehl<s:1>， ISSAC 2016]的更快版本的LLL算法，[Vaidya， FOCS 1989]的体积中心切割平面方法（CPM）及其在[Jiang， Lee, Song, Wong， STOC 2020]中给出的快速实现的非简单组合获得的。对于子模块函数最小化（SFM）的特殊情况，我们的结果表明，使用$O(n^3 \log n)$调用求值oracle和$O(n^4 \log n)$附加算术运算，该问题需要一个强多项式时间算法。对于这个特定问题，我们更通用的算法的oracle复杂性和算术运算的数量都优于之前最著名的运行时算法，如[Lee， Sidford, Wong， FOCS 2015]和[Dadush， v<s:1>, Zambelli, SODA 2018, MOR 2021]。
Given a convex function $f$ on $\mathbb{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 $\widetilde{\Omega}(n^8)$, due to expensive sub-routines such as the Lenstra-Lenstra-Lov\'asz (LLL) algorithm [Lenstra, Lenstra, Lov\'asz, 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\'e, 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 [Lee, Sidford, Wong, FOCS 2015] and [Dadush, V\'egh, Zambelli, SODA 2018, MOR 2021].
DOI：
--
发表时间：
2023
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Chakrabarty, Deeparnab;Graur, Andrei;Jiang, Haotian;Sidford, Aaron
通讯作者：
Sidford, Aaron
影响因子：
1.7
作者：
Dadush D
通讯作者：
Dadush D