Skip to main content
retagged to something which hopefully is more appropriate
Link
Yemon Choi
  • 25.8k
  • 9
  • 69
  • 156
Source Link
eth0
  • 38
  • 3

Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?

Given a set of distances S, choose N unique points P on a number line such that the distances between the N points occur in S as much as possible. That is, maximize the occurence in S of the distances between the N points.

For example:

S = {2, 4}, N = 4

One answer would be P = {2, 4, 6, 8}, since the distances between the points P are 2, 2, 2, 2, 4, 4, 6. Only 6 is not in S.

or

S = {7, 13, 14, 22} N = 4501

answer ???

I'm not looking for an exact answer (although an exact answer wouldn't hurt) but rather I am trying to avoid reinventing the wheel (fun though it may be). What mathematical tools could I use to avoid bruteforcing the possible values of P. How should how would you approach this problem?