• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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