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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Sounds like you are packing your domain with Manhattan spheres. $\endgroup$
    – The Masked Avenger
    Commented May 27, 2014 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
    Commented May 27, 2014 at 22:07
  • $\begingroup$ I don't get your comment at all, may you please detail your idea? $\endgroup$
    – user109711
    Commented May 28, 2014 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
    Commented May 28, 2014 at 6:53

3 Answers 3

Reset to default
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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 1, 2014 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
    Commented Jun 2, 2014 at 18:42
  • $\begingroup$ That's incredibly clear and helpful. Thank you very much for your efforts! $\endgroup$
    – user109711
    Commented Jun 2, 2014 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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 28, 2014 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
    Commented May 28, 2014 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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .