2
$\begingroup$

this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)

Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, M_y, M_z)$ is a given vector.

Select n vectors from $k$ vectors such that: $R_x ≥ M_x , R_y ≥ M_y,$ and $R_z ≥ M_z$.

I am in search of an efficient algorithm/method (something faster than $k^5$, for n = 5) that finds any valid set of n vectors.

$\endgroup$
3
  • $\begingroup$ Here is a link to the MSE question: math.stackexchange.com/q/1161072/166535 (It's always polite to give the link when cross-posting.) $\endgroup$ Mar 3, 2015 at 0:33
  • $\begingroup$ Could you describe/sketch your $n^4$ algorithm? $\endgroup$ Mar 3, 2015 at 0:59
  • $\begingroup$ A greedy heuristic: Sort the vectors by the length of their projection onto $M$, and select the top $n$ of those. But I can see this might result in an $R$ that doesn't dominate $M$, while another selection does dominate $M$. $\endgroup$ Mar 3, 2015 at 1:19

0

Your Answer

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