|
This article is cited in 3 scientific papers (total in 3 papers)
Minimization of even conic functions on the two-dimensional integral lattice
D. V. Gribanov, D. S. Malyshev National Research University Higher School of Economics, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
Abstract:
Under consideration is the Successive Minima Problem for the $2$-dimensional lattice with respect to the order given by some conic function $f$. We propose an algorithm with complexity of $3.32\log_2 R + O(1)$ calls to the comparison oracle of $f$, where $R$ is the radius of the circular searching area, while the best known lower oracle complexity bound is $3 \log_2 R + O(1)$. We give an efficient criterion for checking that given vectors of a $2$-dimensional lattice are successive minima and form a basis for the lattice. Moreover, we show that the similar Successive Minima Problem for dimension $n$ can be solved by an algorithm with at most $O(n)^{2n}\log R$ calls to the comparison oracle. The results
of the article can be applied to searching successive minima with respect to arbitrary convex functions defined by the comparison oracle.
Illustr. 2, bibliogr. 24.
Keywords:
quasiconvex function, convex function, conic function, quasiconvex polynomial, integral lattice, nonlinear integer programming, successive minima, reduced basis of a lattice.
Received: 02.04.2019 Revised: 15.08.2019 Accepted: 28.08.2019
Citation:
D. V. Gribanov, D. S. Malyshev, “Minimization of even conic functions on the two-dimensional integral lattice”, Diskretn. Anal. Issled. Oper., 27:1 (2020), 17–42; J. Appl. Industr. Math., 14:1 (2020), 56–72
Linking options:
https://www.mathnet.ru/eng/da942 https://www.mathnet.ru/eng/da/v27/i1/p17
|
Statistics & downloads: |
Abstract page: | 251 | Full-text PDF : | 67 | References: | 24 | First page: | 6 |
|