Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = 1}\}$. $\cal{S}$ is together with a metric $d$ which corresponds to the Manhattan distance. Let $S$ be a given finite subset of $\cal{S}$ and $u_* \in S$. Let ${\cal S}(u_*) \subseteq {\cal S}$ be the set of all vectors from ${\cal S}$ which are closer to $u_*$ than to any other vector from $S \setminus \{u_*\}$.

Given a positive integer $p$, I would like to be able to compute a finite set $S' \subseteq {\cal S}(u_*)$ of size $p$, such that $S'$ minimizes the function $\max_{v \in {\cal S}(u_*)}{\min_{w \in S'}}{d(v, w)}$.

Roughly, the idea consists in drawing the "Voronoi diagram" on the space ${\cal S}$ built from the finite set of points $S$. Then, one focuses on the "cell" from this diagram associated with the point $u_* \in S$. One wants to solve the $p$-center problem on this cell, i.e., find $p$ points which are "best distributed" inside this cell.

Does anybody know how to solve this problem? Like, whether it is possible to solve the problem using linear programming? Note that the inputs of the problem are $S$, $u_*$ and $p$.

Edit: since the above problem may be out of reach, I'd rather consider the following simpler problem. Let ${\cal S}$ be defined as above and let $p$ be a positive integer, find a set $S' \subseteq {\cal S}$ of size $p$ which minimizes the function $\max_{v \in {\cal S}}{\min_{w \in S'}}{d(v, w)}$. Is there also anyway to encode this problem?

  • $\begingroup$ Try literature of "quantization of probability measures." Though as far as I know it is normally the Euclidean rather than Manhattan metric. $\endgroup$
    – user25199
    Feb 6, 2015 at 18:28


Your Answer

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

Browse other questions tagged or ask your own question.