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

New contributor
Nathan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ Do all orders make sense, though? $\endgroup$ – Yuval Filmus Nov 22 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$ – Nathan Nov 22 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$ – Yuval Filmus Nov 22 at 10:53
  • $\begingroup$ @YuvalFilmus I think that does not matter, we only need to output an optimal solution $\endgroup$ – Nathan Nov 22 at 10:56
  • 1
    $\begingroup$ I suggest trying to follow the hint. $\endgroup$ – Yuval Filmus Nov 22 at 11:02
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

Nathan is a new contributor. Be nice, and check out our Code of Conduct.

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

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