Algorithm for MaxMin diversity problem on hypercube?

Question

The Maximum Minimum Diversity Problem (MMDP) can be roughly stated as follows:

Let $S$ be a set of points, $k \in \mathbb{N}$. Find the $k$-element subset $M$ of $S$ such that the minimal distance $d_M=\min_{x,y\in M, x\neq y} d(x,y)$ between two points in $M$ is maximal (see e.g. this paper for more details).

As far as I've been able to find, in practical applications $S$ will usually be a (finite) cloud of discrete points, from which $k$ points have to be picked in the most efficient manner possible. My question instead is:

Are there efficient algorithms for directly constructing the set $M$ when $S$ is the $n$-dimensional hypercube (or $n$-orthotope)? Both exact and approximate solutions would be helpful.

P.S. As I'm sure one can notice from the post, I'm not a professional mathematician but I thought the question might still be adequate for this forum. Please feel free to edit for notation etc., add tags or move the question somewhere else if this is not the appropriate place.

Answer 1

There is a very large literature on such problems which involve finding configurations which maximize the minimum distance over all fixed sized point sets in some compact metric space.

For a large number of points $k$ and $S$ a hypercube, a good approximate answer can be given by referring to the sphere packing literature (see for instance Conway and Sloane's book Sphere Packings, Lattices and Groups and online databases such as Nebe and Sloane's Lattices page, or Scholl's Sphere Packing Database among other sources). Here one can construct roughly optimal $M$ by taking all lattice points in the hypercube from an appropriately scaled lattice. For low dimensions it is conjectured that the optimal sphere packing density is attained for a lattice packing (where each sphere has as radius half the distance from the closest vector to the origin in the lattice) which has been verified for dimensions $d=2,3,8,$ and $24$, but for dimensions even as small as $d=10$ there are non-lattice packings denser than any known lattice packings (for more information on this see Elkies' survey here from the AMS Notices, although more recent developments answer some of the questions posed there).

For general $k$, to give exact solutions (even in two-dimensions!) may be very difficult. A related problem is of finding best packings of circles of the same radius in a unit square (a simple observation, as by rescaling, to any maximal distance set $M$ with all distances appearing being at least $d<1$, all circles of radius $d$ centered at the $k$ points in $M$ must fit inside the square of length $1+2d$ and be non-overlapping). Several recent papers on this problem appear from M. Locatelli and P. Szabó and their co-authors (see here, here, section two in the first link gives a few equivalents of this problem, one of which is the problem posed in the question). Packomania is a great resource to check best known configurations for particular numbers of points.

For numerical solutions which aim to be exact, many calculations of the large configurations rely on use of stochastic optimization techniques (finally, these can be found in a list of references for the constructions which appear on the packomania webpage).