Compare and find the best match from multiple lists

Question

Lets say I have n lists from different sources, each contains m possible location of the user. I need to choose the most probable prediction of the user location. My idea was to pick one location from each source that so that those n locations are closest to each other. The average of those n locations will be my estimated user location.

My approach so far was to find every combination of n locations of those lists, and choose the smallest cluster. This works however for each prediction I have to iterate m^n times for all the possible combinations. The time complexity becomes too high if i have many sources with many possible locations. Is there a way to achieve what I wanted without iterating through every single combination or is there any other algorithms that does the similar thing even at the cost of reduced accuracy? Any help would be appreciated.

Answer 1

I don't know whether there is a polynomial-time algorithm for this problem that always gives the optimal solution. Below I show a candidate heuristic that might be useful in some settings. For notation, let $L[i,j]$ be the location of the $j$th source in the $i$th list.

• Initialize a queue $Q$ with all of the $L[i,j]$ locations.

• Repeat until $Q$ is empty:

  • Pop the first element of $Q$, and call it $\ell$.

  • For each $i$, let $\ell_i$ be the $L[i,j]$ that is nearest to $\ell$ (where $j$ ranges over all $m$ possibilities).

  • Let $\hat{\ell}$ be the average of the $\ell_i$'s.

  • Measure the "goodness" of $\hat{\ell}$ according your objective function (e.g., $\sum_i \|\hat{\ell}-\ell_i\|_2^2$, or whatever objective function you use).

  • If $\hat{\ell}$ is better than anything seen so far, remember it.

  • If $\hat{\ell}$ has not been previously added to $Q$, append $\hat{\ell}$ to $Q$.

• Output the best location seen during this process.

If you want to spend more computation time in exchange for the possibility of finding more accurate solutions, at initialization you could also add all averages of all pairs of locations from $L$.