2
$\begingroup$

Let $(A, dist)$ be a finite metric space. Consider the following "$p$-center problem": given a positive integer $p$, find a subset $B$of $A$ such that $|B| = p$ and which minimizes the number $\max_{a \in A}\min_{b \in B}{dist(a, b)}$. Assume that we have an oracle $f$ for this problem, i.e., which finds such optimal subset $B = f((A, dist), p)$ for any given finite metric space $(A, dist)$ and positive integer $p$.

Consider now the following algorithm, which takes in input a finite metric space $(A, dist)$, a positive integer $p \geq 2$ and an element $a \in A$:

1) Set $B = f((A, dist), p))$;

2) If $a \in B$ then return. Otherwise goto 3;

3) Select an element $b_* \in B$ which is one of the closest to $a$ with respect to $dist$;

4) Set $A' = \{a \in A \mid \forall b \in B, dist(a, b_*) \leq dist(a, b)\} \setminus \{b_*\}$;

5) Set $A = A'$ and goto 1);

Intuitively, this algorithm seeks for a given point $a \in A$ by solving iteratively the $p$-center problem by reducing the search space $A$ at each step. It is useful, e.g., in Product Configuration, when a user wants to reach her preferred product, but doesn't want to browse the (possibly large) catalog $A$. Step 1 finds a "well-distributed" set $B$ of $p$ elements among the set $A$ (using $f$). If one of the points in $B$ is the preferred one, then the algorithm stops in Step 2. Otherwise, the (rational) user just picks the element $b_*$ from $B$ which is the closest to her ideal one; this is automatically done in Step 3. In Step 4 and Step 5, one removes the element $b_*$ from the set $A$, and one further reduces $A$ only to its elements which are closer to $b_*$ than to any other element from $B$. The algorithm iterates the process on the restricted set $A$.

It is easy to see that the algorithm terminates at most after $|A|$ iterations, since one element at least ($b_*$) is removed from it at each iteration.

The question is: can we have a tighter upper bound of number of iterations? Like, a logarithmic number of iterations in the size of $A$ or the diameter of $A$.

I know that in the case where for some constant number $\alpha$, if we have $\forall a_1, a_2 \in A$, $dist(a_1, a_2) = \alpha$, then the number of iterations is not logarithmic but linear in the size of $|A|$, but this is a very specific case. One can make some assumptions like, e.g., the number of elements in $A$ which have the same pairwise distance is bounded by some number $k$.

$\endgroup$
  • $\begingroup$ I think that, even if all pairwise distances are distinct ($k=1$), you can still have a linear number of queries. E.g. take $p = 2$ and consider the set of $n$ points $A=\{1, 2, 4, \ldots, 2^n\}$ on the line with Euclidean distance. Take $a=1$. At the first query, the oracle will return centers $2^n$ and $2^{n-2}$, so $A'$ will be $\{1, 2, 4, \ldots, 2^{n-3}\}$. So, inductively, you get $n/3$ queries. And for $p>2$, doesn't the same example give $\Omega(n/p)$ queries? $\endgroup$ – Neal Young Mar 10 '15 at 5:43

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.