Эта публикация цитируется в
3 статьях
Минимизация чётных конических функций на двумерной целочисленной решётке
Д. В. Грибанов,
Д. С. Малышев Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
Аннотация:
Рассматривается задача построения последовательных минимумов двумерной целочисленной решётки относительно порядка, заданного некоторой конической функцией
$f$. Для указанной задачи предлагается алгоритм со сложностью
$3{,}32 \log_2 R + O(1)$ обращений к оракулу сравнения функции
$f$, где
$R$ — радиус круговой области поиска, тогда как нижняя оценка сложности на данный момент составляет
$3 \log_2 R + O(1)$. В настоящей работе приводится эффективный критерий проверки того, что заданные векторы двумерной решётки являются последовательными минимумами и образуют базис решётки. Также показывается, что аналогичная задача поиска последовательных минимумов для решёток размерности
$n$ может быть решена алгоритмом, использующим не более чем
$O(n)^{2n}\log R$ обращений к оракулу сравнения. Результаты работы могут быть применены для поиска последовательных минимумов относительно любых выпуклых функций, заданных оракулом
сравнения. Ил. 2, библиогр. 24.
Ключевые слова:
квазивыпуклая функция, выпуклая функция, коническая функция, квазивыпуклый полином, целочисленная решётка, нелинейное целочисленное программирование, последовательные минимумы решётки, приведённый базис решётки.
УДК:
519.854 Статья поступила: 02.04.2019
Переработанный вариант: 15.08.2019
Принята к публикации: 28.08.2019
DOI:
10.33048/daio.2020.27.654