# Minimum sum of squared Euclidean distance between two arrays

Question:
Given two sorted sequences in increasing order, $$X$$ and $$Y$$. $$Y$$ is of size $$k$$ and $$X$$ is of size $$m$$.
I would like to find a subset of $$X$$, $$i.e$$, $$X'$$ of size $$k$$, and considering the following optimization problem:$$d(Y,X') = \sum_{j=1}^{k}(y_{j}-x'_{j})^{2}$$ And $$X'$$ is a subset of $$X$$ of size $$k$$, $$y_{j} \text{ and } x'_{j}$$ is element in $$Y$$ and $$X'$$. I would like to find the subset of $$X$$, to reach the minimum of $$d(Y,X')$$.
Note that $$X'$$ could have $$k!$$ numbers of arrangements, so its order is totally unknown.

What I have came up with so far:
I would like to approach it using Dynamic Programming, and I think I would first compute the squared distance between each element in $$Y$$ and $$X$$, but I'm having trouble in determining what is the subproblem and how to solve ths using DP. Thank you!

Update: The $$X'$$ could be sorted, which means we could aim at finding a sorted subset of $$X$$.

• Do all orders make sense, though? – Yuval Filmus Nov 22 '20 at 10:28
• @YuvalFilmus so the order could be random, what I would like to find is a subset of X with length k, and it can be any order – Nathan Nov 22 '20 at 10:30
• I understand that the subset of $X$ could be ordered in an arbitrary way. I'm just not sure that all orders can actually occur in an optimal solution. – Yuval Filmus Nov 22 '20 at 10:53
• @YuvalFilmus I think that does not matter, we only need to output an optimal solution – Nathan Nov 22 '20 at 10:56
• I suggest trying to follow the hint. – Yuval Filmus Nov 22 '20 at 11:02

## 1 Answer

for m' = 0 to m for k' = max(0, m-m') to min(m', k) Take the problem of the first m' items of X and the first k' items of Y. Find the value of the smallest sum, and whether X[m'] is in that sum.

The optimal subset of the first m' items of X is either the best subset of the first m'-1 items of X matching the first k' items of Y, or the best subset of the first m'-1 items of X matching the first k'-1 items of Y, with X[m'] and Y[k'] added.

Note that sets and subsets are not sorted. If you want the indexes in arbitrary order, sorting X and Y first should work.