1
$\begingroup$

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).

$\endgroup$
1

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

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

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