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

При некоторых условиях на ранг тензора или на его 2-ранг, определяемый аналогичным образом, построены полиномиальные алгоритмы вычисления относительных инвариантов полной линейной группы $GL$. Показано, что если ограничения на ранг несколько ослабить, то задача вычисления относительного инварианта степени 1 становится полиномиально эквивалентной задаче вычисления этого функционала для тензора общего положения. Для исследуемых комбинаторных проблем (задачи о взвешенных разбиениях и покрытиях) максимум целевой функции есть предел статистической суммы, которая оказывается относительным инвариантом группы $GL$. В некоторых частных случаях предложены полиномиальные алгоритмы подсчета этих сумм.
Библиогр. 10 назв.