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

Рассматриваются задачи поиска $\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$ являются орбитами или объединениями некоторых орбит точек в некотором представлении симметрической группы. При этом вычисление упомянутых сумм ввиду двойственности Вейля сводится к вычислению определителя, пфаффиана, функций Шура, инвариантов полной линейной группы. Приведены следствия для классических задач комбинаторной оптимизации (обычная и квадратичная задачи о назначениях, задача о разбиениях, о поиске максимума квадратичной формы в целочисленных точках многогранника).