Suppose we have a similarity measure s : String x String -> [0, 1] and sets K, L in String with |K| <= |L|. The task is to find an injection f : S -> T such that Sum({s(k, f(k)) | k in K}) is maximised. That is, f should be an injection which maximises similarity.

My naive approach would be to compute all the similarities s(k, l) at once, then use a polynomial time bipartite graph matching algorithm such as the Hungarian algorithm or Ford-Fulkerson algorithm to compute an optimal matching. Here, I would have s be the n-gram similarity function from Kondrak's "N -gram similarity and distance" paper.

Does anyone know of a cheaper way to go about this? I'm hoping for something which considers the whole sets, rather than pairwise similarity alone.

  • 1
    $\begingroup$ You haven't stated any restrictions on the similarity measure s, so any faster-than-HA-and-FF algorithm that you could find to solve this problem would in essence be a faster-than-HA-and-FF algorithm for bipartite matching. In detail: any bipartite graph could be converted to an instance of your problem by mapping all vertices to distinct dummy strings, and specifying s as an $n$-by-$n$ matrix with rows and columns each indexed by these strings. I don't know of lower bounds for bipartite matching, so such an algorithm might conceivably exist, but it would be a major result in CS. $\endgroup$ – j_random_hacker May 5 '17 at 17:58
  • $\begingroup$ Firstly, thank you for the answer and sorry for taking so long to reply. I was wondering whether it was possible to take a different approach, rather than simply computing all similarities and then using an existing bipartite graph matching algorithm. I thought there might be some solution which involves growing a matching over approximated (more cheaply computed) similarities, improving the matching and similarity approximations over time. Maybe an adapted HA. I know there might not be a definitive answer to this, but suggestions in the right direction would be appreciated. $\endgroup$ – justinpc May 11 '17 at 10:34

Your Answer

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

Browse other questions tagged or ask your own question.