Geodesic
Minimization of even conic functions on~the~two-dimensional integral lattice
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 17-42

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : quasiconvex function, quasiconvex polynomial
Keywords: convex function, conic function, integral lattice, nonlinear integer programming, successive minima, reduced basis of a lattice. 
@article{DA_2020_27_1_a1,
     author = {D. V. Gribanov and D. S. Malyshev},
     title = {Minimization of even conic functions on~the~two-dimensional integral lattice},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--42},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/}
}
TY  - JOUR
AU  - D. V. Gribanov
AU  - D. S. Malyshev
TI  - Minimization of even conic functions on~the~two-dimensional integral lattice
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 17
EP  - 42
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/
LA  - ru
ID  - DA_2020_27_1_a1
ER  - 
%0 Journal Article
%A D. V. Gribanov
%A D. S. Malyshev
%T Minimization of even conic functions on~the~two-dimensional integral lattice
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 17-42
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/
%G ru
%F DA_2020_27_1_a1
D. V. Gribanov; D. S. Malyshev. Minimization of even conic functions on~the~two-dimensional integral lattice. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 17-42. http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/