С. И. Веселов, Д. В. Грибанов, Н. Ю. Золотых, А. Ю. Чирков, “Минимизация симметричной квазивыпуклой функции на двумерной решётке”, Дискретн. анализ и исслед. опер., 2018, том 25, выпуск 3,страницы 23

Эта публикация цитируется в 4 статьях

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

С. И. Веселов, Д. В. Грибанов, Н. Ю. Золотых, А. Ю. Чирков

Институт информационных технологий, математики и механики, Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия

Аннотация: Рассматривается задача минимизации симметричной квазивыпуклой функции, заданной оракулом на множестве целых точек квадрата. Сформулирован критерий оптимальности решения, получена логарифмическая нижняя оценка сложности задачи и разработан алгоритм, у которого число обращений к оракулу превышает нижнюю оценку не более чем в 3 раза. Библиогр. 14.

Ключевые слова: квазивыпуклая функция, оракул, целочисленная решётка.

УДК: 519.854

Статья поступила: 06.07.2017
Переработанный вариант: 15.12.2017

DOI: 10.17377/daio.2018.25.585