3
$\begingroup$

Given a non-negative integer $m$, let $\Omega_m$ denote the set of vectors $\omega = (\omega_1, \dots, \omega_m) \in [0, 1]^m$ such that $\sum_i{\omega_i} = 1$. The set $\Omega_m$ is together with a metric $d_M$, that is the Manhattan distance between vectors, i.e., $\forall \omega, \omega' \in \Omega_m$, $d_M(\omega, \omega') = \sum_i{|\omega_i - \omega'_i|}$. Given $S \subseteq \Omega_m$, we denote $\min(d_M, S) = \min_{\omega, \omega' \in S}{d_M(\omega, \omega')}$.

I am interested in the following ``most diverse $k$-subset'' problem: given two non-negative integers $m, k$, return a set $S \subset \Omega_m$ of size $k$ that maximizes $\min(d_M, S)$ (i.e., $S$ is such that $\forall S' \subset \Omega_m$ with $|S'| = k$, we have $\min(d_M, S') \leq \min(d_M, S)$).

For example, if $m = 3$ and $k = 4$, it seems that the only possible resulting set is $S = \{(0, 0, 1), (0, 1, 0), (1, 0, 0), (1/3, 1/3, 1/3)\}$, with $\min(d_M, S) = 4/3$.

What would be the general algorithm to compute $S$, for all non-negative integers $m, k$?

$\endgroup$
  • $\begingroup$ Sounds like you are packing your domain with Manhattan spheres. $\endgroup$ – The Masked Avenger May 27 '14 at 22:01
  • $\begingroup$ Since the spheres tile nicely in small dimensions, you may get good bounds just using volume comparisons. $\endgroup$ – The Masked Avenger May 27 '14 at 22:07
  • $\begingroup$ I don't get your comment at all, may you please detail your idea? $\endgroup$ – user109711 May 28 '14 at 6:36
  • 1
    $\begingroup$ A general algorithm computing $S$ given $m,k$ may be out of reach. This problem includes the classification of all optimal binary codes as a sub-problem. (I suppose exhaustive search works in that case, but this is presumably not what you're after.) Masked Avenger's comment on volumes can help obtain bounds on the largest minimum distance. $\endgroup$ – Peter Dukes May 28 '14 at 6:53
3
$\begingroup$

In the case $m=3$, I've used an SMT-solver (MathSAT 5) to find the optimal solutions for $k = 4$ to $8$. If my programming is correct, here they are:

$k = 4$: $\min(d_M,S) = 4/3$ for $[0,0,0],[0,1,0],[1,0,0],[1/3,1/3,1/3]$:

enter image description here

$k = 5$: $\min(d_M,S) = 1$ for $[0,1/2,1/2],[1/2,1/2,0],[1,0,0],[1/2,0,1/2],[0,0,1]$

enter image description here

$k = 6$: $\min(d_M,S) = 1$ for $[1/2,0,1/2],[1,0,0],[0,0,1],[1/2,1/2,0],[0,1/2,1/2],[0,1,0]$

enter image description here

$k = 7$: $\min(d_M,S) = 4/5$ for $[1/5,3/5,1/5],[0,1,0],[0,2/5,3/5],[1,0,0],[3/5,11/40,1/8],[9/20,1/40,21/40],[1/20,0,19/20]$

enter image description here

$k= 8$: $\min(d_M,S) = 3/4$ for $[5/8,3/8,0],[5/8,0,3/8],[1/4,1/8,5/8],[0,1/2,1/2],[1/4,5/8,1/8],[0,1,0],[1,0,0],[0,0,1]$

enter image description here

$\endgroup$
  • $\begingroup$ Thank you very much for these results. That would be great if I could see how your coding in mathsat5 looks like. I fail to find how to encode an optimization problem in it. $\endgroup$ – user109711 Jun 1 '14 at 20:39
  • $\begingroup$ @user109711: I've put more material on this, including examples of mathSAT 5 input and output, and optimal solutions up to $k=16$, on my web site math.ubc.ca/~israel/packing/index.html $\endgroup$ – Robert Israel Jun 2 '14 at 18:42
  • $\begingroup$ That's incredibly clear and helpful. Thank you very much for your efforts! $\endgroup$ – user109711 Jun 2 '14 at 22:08
1
$\begingroup$

To expand upon the commentary, consider placing k instances of a certain kind of region in a unit square. These are called packing problems, with two popular instances involving circles in a square and another involving (non axis-aligned) congruent small squares in a square. Exact solutions for small k and proofs of optimlity are elusive, but k times the volume of a region cannot exceed the volume of the unit square, and there is often a scaling factor s (and accompanying proof) that says k times the volume of a scaled down version of the region is feasible, and s is often not far from 1.

In your case you have a large simplex to pack with regions I call Manhattan spheres, which I imagine for high dimensions are generalized octahedra. They aren't rotatable as in the above packing problem with square regions, but you can perform the volume computations just the same. This will help you figure the radius of the sphere to within the scaling factor, which leaves the problem of placement. From an initial placement with small radius of k regions, some dynamic algorithms based on charge-repulsion (think of simultaneously blowing up k balloons in a box and watch them move around) often lead to near optimal placements.

$\endgroup$
  • $\begingroup$ Note that you are not quite packing in the simplex because the spheres don't have to be contained in the simplex, just their centres. So it's packing in a somewhat larger region, the union of all spheres whose centres are in the simplex. $\endgroup$ – Robert Israel May 28 '14 at 18:13
  • $\begingroup$ Indeed. Once a good value for the radius is gotten, one can usually scale the box so that a scaled box packing yields the desired placement in the unscaled box. There may be an advantage in using the sphere union after trying a packing derived from a scaled box. $\endgroup$ – The Masked Avenger May 28 '14 at 18:21
0
$\begingroup$

It seems that if $m<<k$ ( $k$ is so larger than $m$), the minimum is between $1/n$ and $1/(n+1)$, when $n$ is a number that satisfies

$n+m-1 \choose n$$\leq k \leq$$ n+m \choose n+1$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.