Задача формулируется предельно просто и чем-то напоминает вычисление дискриминанта.
Есть матрица с положительно определёнными элементами:


и

Требуется вычислить минимальную сумму:

Где минимизация ведётся по всевозможным перестановкам:

для

и

Так как число перестоновок равно

то прямой поиск минимума для больших матриц - задача экспоненциальной сложности,
и у меня вопрос, как найти минимум с полиномиальным числом операций.
Наверняка существуют алгоритмы типа метода Гаусса для вычисления дискриминантов.