# Given arrays A & B and an element-wise distance function f between them, minimize the sum of f over A & B by reordering B?

I have a problem I think I've managed to distill down to the following problem:

Given two arrays $$A$$ and $$B$$ of length $$n$$ and a pair-wise distance function $$f(a_i, b_i)$$, where $$a_i \in A$$ and $$b_i \in B$$, reorder the elements in $$B$$ to minimize $$\sum_i{f(a_i,b_i)}$$

In my case $$f$$ is a distance function on strings (the ROUGE metric to be exact) and as far as I can figure out it doesn't have a useful substructure (e.g., it isn't monotonic) that could lend itself well to, e.g., dynamic programming.

A worst case solution would take $$O(n!)$$ time by trying all permutations of $$B$$ (after computing a distance metric lookup table for $$f$$ in $$O(n^2)$$ time).

This is indeed an instance of the assignment problem, as you speculated. There is one left-vertex per element of $$A$$, and one right-vertex per element of $$B$$, and the weight of the edge between vertices $$a_i,b_i$$ is given by $$f(a_i,b_i)$$. You are looking for a perfect matching of minimum weight, which can by solved by any algorithm for the assignment problem. In particular, the problem can be solved in polynomial time.