论文标题
多项式算法，用于最大程度地减少固定尺寸的离散换句函数
A polynomial algorithm for minimizing discrete convic functions in fixed dimension
论文作者
论文摘要
最近引入了圆锥和离散锥体功能类。在本文中，我们使用consic术语代替圆锥。旋转功能的类别正确包括凸函数的类别，严格的准准词函数和Quasiconvex多项式的类别。另一方面，旋转函数类别已正确包含在Quasiconvex函数类别中。离散的换句函数是对信用函数的离散类似物。最近，获得了在某些$ n $ dimentional drafius $ρ$的整数上定义的最小值oracle的呼叫数量的下限$ 3^{n-1} \ log（2ρ-1）$。但是，对于最小化此类功能的多项式存在（固定$ n $的$ \logρ$）的问题仍然开放。在本文中，我们积极回答了这种算法存在的问题。也就是说，我们提出了一种用于最小化离散的换句函数的算法，该算法使用$ 2^{o（n^2 \ log n）} \ logρ$调用oracle比较，并且具有$ 2^{o（n^2 \ log n）} \ mbox {\ mbox {poly}（py poly}（\ logρ）$ bit Complectity。
Recently classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. Recently the lower bound $3^{n-1}\log (2 ρ-1)$ for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some $n$-dimensional ball with radius $ρ$ was obtained. But the problem of the existence of a polynomial (in $\logρ$ for fixed $n$) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses $2^{O(n^2 \log n)} \log ρ$ calls to the comparison oracle and has $2^{O(n^2 \log n)} \mbox{poly }(\log ρ)$ bit complexity.
