0
$\begingroup$

$\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity

$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$

of some string of symbols $x \in \Sigma^n$ solely through permuting $x$? That is, finding

$$\underset{\sigma\in S_n}{\argmin}\ g(\sigma(x))$$

$f: \Sigma \times \Sigma \to \mathbb{R}$ is here a black-box function with no other properties.

$\endgroup$
  • $\begingroup$ The problem is polynomial-time solvable if $\Sigma$ is of constant size; namely, there is an algorithm with running time $n^{O(|\Sigma|)}$. If $\Sigma$ can be of arbitrary size, the problem is NP-hard (see Tim's answer). $\endgroup$ – Yury Sep 24 '19 at 22:39
3
$\begingroup$

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set.

Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one can obtain the desired permutation using a topological sort, and the corresponding value of $g$ will be the size of the feedback arc set.

Moreover, the problem of deciding whether there is a permutation $\sigma$ with $g(\sigma(x))\leq k$ is in NP: just guess the permutation and compute $g$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.