AhmadYahya's blog

By AhmadYahya, history, 3 weeks ago, In English,


If I have 2 arrays of frames, namely, A and B. Each element of an array represents a frame.

and a function calc_sim(frame_i, frame_j) that measures the similarity between two frames.

frame_i and frame_j are matched if their similarity is above 50%.

How can one measure the maximum number of matched pairs between the arrays A and B (of course knowing that if an element is already in a pair, it can’t be used again)?

A greedy solution won’t work here because choosing a frame may affect badly other frames, and the only optimal solution I can think of is trying all the possibilities which is O(n!).

Is there a better solution or is it an NP problem?

Thanks in advance.

  • Vote: I like it
  • +11
  • Vote: I do not like it

3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Google about Maximum Matching in Bipartite Graphs.