RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и анализ // Архив

Алгебра и анализ, 1992, том 4, выпуск 1, страницы 3–53 (Mi aa298)

Обзоры

Статистические суммы в оптимизации и вычислительных задачах

А. И. Барвинок

Институт эволюционной физиологии и биохимии им. И. М. Сеченова РАН

Аннотация: Применение метода статистических сумм в задаче поиска $\max\{f(x):x\in X\}$, где $X$ – множество, $f\colon X\to\mathbb R$ – функция, основано на вычислении интеграла $\int_X\exp\{f(x)\}\,d\mu$ для подходящего заряда $\mu$ на $X$. Во многих важных случаях интеграл обладает полезными алгебраическими свойствами, позволяющими быстро его вычислить. Приведены следствия для задач комбинаторной и дискретной оптимизации, приложения к нелинейному программированию, к проблемам вычисления объема и подсчета целых точек. Обсуждаются связи с теорией инвариантов, алгебраической геометрией, теорией модулярных форм.

Ключевые слова: статистическая сумма, экспоненциальная сумма, экспоненциальный интеграл, комбинаторная оптимизация, вычислительная сложность.

Поступила в редакцию: 23.05.1991


 Англоязычная версия: St. Petersburg Mathematical Journal, 1993, 4:1, 1–49

Реферативные базы данных:


© МИАН, 2024