1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Do all orders make sense, though? $\endgroup$ Nov 22, 2020 at 10:28
  • $\begingroup$ @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 $\endgroup$
    – codeMike
    Nov 22, 2020 at 10:30
  • $\begingroup$ 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. $\endgroup$ Nov 22, 2020 at 10:53
  • $\begingroup$ @YuvalFilmus I think that does not matter, we only need to output an optimal solution $\endgroup$
    – codeMike
    Nov 22, 2020 at 10:56
  • 1
    $\begingroup$ I suggest trying to follow the hint. $\endgroup$ Nov 22, 2020 at 11:02

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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