Diskretnyi Analiz i Issledovanie Operatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2020, Volume 27, Issue 1, Pages 17–42 (Mi da942)

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.

 Funding Agency Grant Number Russian Foundation for Basic Research 18-31-20001_ìîë_à_âåä This research is supported by Russian Foundation for Basic Research (Project 18–31–20001–mol-a-ved).

DOI: https://doi.org/10.33048/daio.2020.27.654

Full text: PDF file (414 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 56–72

UDC: 519.854
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

Citation in format AMSBIB
\Bibitem{GriMal20} \by D.~V.~Gribanov, D.~S.~Malyshev \paper Minimization of even conic functions on~the~two-dimensional integral lattice \jour Diskretn. Anal. Issled. Oper. \yr 2020 \vol 27 \issue 1 \pages 17--42 \mathnet{http://mi.mathnet.ru/da942} \crossref{https://doi.org/10.33048/daio.2020.27.654} \transl \jour J. Appl. Industr. Math. \yr 2020 \vol 14 \issue 1 \pages 56--72 \crossref{https://doi.org/10.1134/S199047892001007X} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85082402367}