RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Алгебра и анализ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Алгебра и анализ, 1990, том 2, выпуск 5, страницы 63–79 (Mi aa206)  

Статьи

Метод статистических сумм в задачах комбинаторной оптимизации

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

Ленинградский институт эволюционной физиологии и биохимии им. И. М. Сеченова

Аннотация: Рассматриваются задачи поиска $\mathrm{max}\{f(x):x\in X\}$, где $X$ – конечное подмножество евклидова пространства $V$, а $f$ – сужение на множество $X$ полиномиального функционала $F\colon V\to\mathbb R$, а также поиска кратности $\mu(f^{-1}(\mathsf a))$ данного значения $\mathsf a\in\mathbb R$ функции $f$ относительно некоторого заряда $\mu$ на множестве $X$. Для решения этих задач используется вычисление сумм
$$ \sum_{x\in X}\exp\{f(x)\}\mu(x),\quad\sum_{x\in X}f^m(x)\mu(X). $$
Выделен и исследован класс множеств $X$ с зарядами $\mu$, для которых первая сумма может быть эффективно вычислена для любого линейного функционала $F$. В приводимых примерах множества $X$ являются орбитами или объединениями некоторых орбит точек в некотором представлении симметрической группы. При этом вычисление упомянутых сумм ввиду двойственности Вейля сводится к вычислению определителя, пфаффиана, функций Шура, инвариантов полной линейной группы. Приведены следствия для классических задач комбинаторной оптимизации (обычная и квадратичная задачи о назначениях, задача о разбиениях, о поиске максимума квадратичной формы в целочисленных точках многогранника).

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

Полный текст: PDF файл (962 kB)

Англоязычная версия:
Leningrad Mathematical Journal, 1991, 2:5, 987–1002

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

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

Образец цитирования: А. И. Барвинок, “Метод статистических сумм в задачах комбинаторной оптимизации”, Алгебра и анализ, 2:5 (1990), 63–79; Leningrad Math. J., 2:5 (1991), 987–1002

Цитирование в формате AMSBIB
\RBibitem{Bar90}
\by А.~И.~Барвинок
\paper Метод статистических сумм в~задачах комбинаторной оптимизации
\jour Алгебра и анализ
\yr 1990
\vol 2
\issue 5
\pages 63--79
\mathnet{http://mi.mathnet.ru/aa206}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1086445}
\zmath{https://zbmath.org/?q=an:0736.90060}
\transl
\jour Leningrad Math. J.
\yr 1991
\vol 2
\issue 5
\pages 987--1002


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/aa206
  • http://mi.mathnet.ru/rus/aa/v2/i5/p63

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Алгебра и анализ
    Просмотров:
    Эта страница:217
    Полный текст:107
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020