Минимизация чётных конических функций на двумерной целочисленной решётке

Рассматривается задача построения последовательных минимумов двумерной целочисленной решётки относительно порядка, заданного некоторой конической функцией $f$. Для указанной задачи предлагается алгоритм со сложностью $3{,}32 \log_2 R + O(1)$ обращений к оракулу сравнения функции $f$, где $R$ — радиус круговой области поиска, тогда как нижняя оценка сложности на данный момент составляет $3 \log_2 R + O(1)$. В настоящей работе приводится эффективный критерий проверки того, что заданные векторы двумерной решётки являются последовательными минимумами и образуют базис решётки. Также показывается, что аналогичная задача поиска последовательных минимумов для решёток размерности $n$ может быть решена алгоритмом, использующим не более чем $O(n)^{2n}\log R$ обращений к оракулу сравнения. Результаты работы могут быть применены для поиска последовательных минимумов относительно любых выпуклых функций, заданных оракулом сравнения. Ил. 2, библиогр. 24.