Optimization Problem

Hello. I am trying to solve the following problem:

We have a set of n points, S
We have a distance matrix D that gives the distance between any two
points in S
We must choose m points from S such that the minimum distance between
any two elements is maximized.

In simpler language, find the m points that are the most spread out.

A really simple way to do this is to try all C(m,n) combinations and
see which one has the greatest minimum distance between two points.
However, this is grossly inefficient. I am working with a set of data
where n is about 1700 and m is about 100.

Are there any algorithms to find the optimal subset? Does anyone have
any suggestions for an approximately optimal algorithm?

Jeffrey Cameron

.

Relevant Pages

  • Re: Point charges inside a sphere
    ... distance ratio problem, the triangular faces which connect the ... For the 8 points on the surface of a sphere with a maximum minimum ... packing unit spheres in the smallest possible sphere, the minimum distance ...
    (sci.math)
  • gfortran ---problem with random umber
    ... '(1x,"Minimum distance between any two particle is",1x,f6.4)'), ... ATOM GREATER THEN RCUT ... Subroutine to apply periodic ... Minimum distance between any two particle is 1.5000 ...
    (comp.lang.fortran)
  • Re: Optimization Problem
    ... We have a distance matrix D that gives the distance between any two ... We must choose m points from S such that the minimum distance between ... any suggestions for an approximately optimal algorithm? ...
    (sci.math)
  • Re: straightness and flatness algorithm
    ... does not occur for a two-dimensional facet ... edges contained in the two respective parallel planes. ... distance occurs between opposite pairs of edges, ... find the minimum distance of the viable sets of planes. ...
    (comp.soft-sys.matlab)
  • Re: Optimization Problem
    ... We have a distance matrix D that gives the distance between any two ... We must choose m points from S such that the minimum distance between ... any suggestions for an approximately optimal algorithm? ...
    (sci.math)