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?

  • $\begingroup$ 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$. $\endgroup$ Jan 5, 2022 at 22:18
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Jan 5, 2022 at 22:59
  • $\begingroup$ @D.W. Good heuristics, I guess, assuming that exact algorithms are inefficient ($n^m$ steps) $\endgroup$
    – MWB
    Jan 5, 2022 at 23:09
  • $\begingroup$ Is there any structure to W at all? $\endgroup$
    – TickaJules
    Jan 5, 2022 at 23:13
  • $\begingroup$ @TickaJules For the purposes of this question, $W$s are arbitrary. $\endgroup$
    – MWB
    Jan 5, 2022 at 23:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.