# minimizing a pairwise sum with respect to a sequence of integers

Let $$m$$ and $$n$$ be two integers, where $$m \leq n$$. Suppose you are given $$m^2$$ matrices $$W^{i,j} \in \mathbb{R}^{n \times n}$$ for $$i, j \in \{1, \dots, m\}$$.

The goal is to find a sequence $$a$$ of $$m$$ integers $$a_i \in \{1, \dots, n\}$$ minimizing

$$\min_a \sum_{i=1}^m \sum_{j=1}^m W^{i,j}_{a_i, a_j}$$

Does this problem have an established name?

The total enumeration takes $$n^m$$ steps. I'm interested in $$m \approx 10$$ and $$n \approx 100$$, if not larger. So I wonder if there are better algorithms that should work here aside from simulated annealing and genetic algorithms?

• This seems to be a long shot, but you could try to reduce SAT to this problem in such a way that SETH-conjecture implies the time lower-bound you specified (assuming negative results). For that given a formula of $N$ variables, you should build an instance such that $m \log n = N$. Jan 5, 2022 at 22:18
• Are you looking for an algorithm that gives the exact optimum, or heuristics that give a pretty-good solution but may or may not give the optimal solution?
– D.W.
Jan 5, 2022 at 22:59
• @D.W. Good heuristics, I guess, assuming that exact algorithms are inefficient ($n^m$ steps)
– MWB
Jan 5, 2022 at 23:09
• Is there any structure to W at all? Jan 5, 2022 at 23:13
• @TickaJules For the purposes of this question, $W$s are arbitrary.
– MWB
Jan 5, 2022 at 23:15