Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1:


Each point is assigned with a weight (possible negative):

$[w(0,1) = 1, w(1,0) = 2,w(0.707,0.707) = -1,w(0.707,-0.707)= -2,...]$

Suppose the standard deviation of the points are defined as the top answer here: https://stats.stackexchange.com/questions/13272/2d-analog-of-standard-deviation

Find a subset of points $S$ such that SUM(w)×STD is maximized.

My gut feeling is that this problem is NP hard. Very similar to knapsack problem. However, knapsack use weight as a threshold. I'm not sure how to transfer the standard deviation here. Any thought on how to prove this would be appreciated!

  • $\begingroup$ Depends on what u mean by STD here? all points have distance 1 from (0,0) so they r on a circle of raduis 1. It seems u should calculate the STD according to the weight values compared to the expected weight of all points, is that what u mean??? $\endgroup$ – ShAr May 11 '20 at 20:36
  • $\begingroup$ Hi ShAr, STD is defined in the link above. STD and weight are two independent factors, which we want to find a set of points whose product of two factors are maximized. Yes, points are on a circle of radius 1. The intuition behind is that, we want to find a set of points with maximum weight, and at the same time hope they are dispersed in the plane. $\endgroup$ – Zachary HUANG May 12 '20 at 21:54

Your Answer

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

Browse other questions tagged or ask your own question.