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

Рассматривается ряд классических комбинаторных задач оптимизации (задачи о назначениях, о взвешенных разбиениях, о коммивояжере, о $k$-сочетаниях), формулируемых как задачи поиска максимума вещественной функции $f$, заданной на симметрической группе $S_n$, а также задачи о поиске максимума $f$ на некотором подмножестве группы $S_n$ и о нахождении кратности данного значения функции относительно некоторого заряда $\mu$ на группе. Для решения этих задач предлагается метод, состоящий в вычислении $m$-го момента функции $f$ и интеграла
$$ S_\mu(f,t)=\sum_{g\in S_n}\exp{tf(g)}\mu(g), \quad t\in\mathbb R. $$
Построены приближенные алгоритмы субэкспоненциальной по $n$ сложности для некоторых частных случаев рассматриваемых задач. В задачах о назначениях и взвешенных паросочетаниях найден класс зарядов, для которых существует псевдополиномиальный алгоритм определения кратностей значений функции $f$. Для этих же задач построены алгоритмы нахождения максимума $f$ на открытом по Зарисскому подмножестве группы $S_n$ (как алгебраической группы), требующие выполнения полиномиального по $n$ числа арифметических действий, сравнения вещественных чисел и взятия экспонент. В ряде случаев такие алгоритмы будут псевдополиномиальными. Для задачи о взвешенных разбиениях и $k$-сочетаниях вычисление выражения $S_\mu(f,t)$ при подходящем заряде $\mu$ сводится к вычислению инвариантов соответственно полилинейной и билинейной формы. В последнем случае предложен алгоритм вычисления такого инварианта.