• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Minimization of even conic functions on the two-dimensional integral lattice

Journal of Applied and Industrial Mathematics. 2020. Vol. 14. No. 1. P. 56-72.

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_2(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.