2
$\begingroup$

Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the cost of assigning all points of $P$ to $c^\star$(the sum of the distances of all points of $P$ to $c^\star$).

For $j\in \{1,2\}$, let $c_j^\star$ is the optimal 1-median of $P_j^\star$ and and let $\hat{c}$ is the optimal 1-median of the 2-point set $\{c_1^\star,c_2^\star\}$. Let $\hat{opt}$ be the cost of assigning all point of $P$ to $\hat{c}$.

My question is that

  1. Does the ratio $\frac{\hat{opt}}{opt^\star}$ is bounded from above by some quantity or there exists "bad" instances (perhaps low dimensional) where it is lower bounded? (My guess is that the latter is true)
  2. What is the situation for finite metric spaces?
  3. What about the "means" or the centroid?

The obvious motivation for the question is that if the "divide and conquer" strategy works for the problem : Given a finite point set, partition it and compute the medians for each partion and the output the median of medians.

$\endgroup$
3
  • 2
    $\begingroup$ For the given motivation, wouldn't you need to allow $c^\star_1$ and $c^\star_2$ to be (recursively computed) approximate solutions to the subproblem? Assuming the median is required to be in the set (so that $c^\star_1$ and $c^\star_2$ are both optimal medians for $\{c^\star_1, c^\star_2\}$), that recursive algorithm can give an approximation factor as high as $n$, even in $\mathbb R^1$. As for Question 3, isn't the centroid of the two centroids of $P_1$ and $P_2$ also the centroid of $P_1\cup P_2$? $\endgroup$
    – Neal Young
    Oct 5, 2021 at 16:07
  • 1
    $\begingroup$ @NealYoung thank you for the comment. Yes you are right regarding question 3. And as for question 1, there are approximation alg for k-median that finds an approximately optimal solution (not necessarily in the input set) with runtime f(k,$\epsilon$).nd, I was actually thinking about those algorithms. $\endgroup$ Oct 5, 2021 at 16:16
  • $\begingroup$ @SudiptaRoy This technique is used in general to design streaming algorithms for the $k$-median/means problem. You may want to see this paper: Algorithm 3 on Page 5. $\endgroup$ Oct 5, 2021 at 20:30

1 Answer 1

2
$\begingroup$

Let $opt^{*}(P_{1})$, $opt^{*}(P_{2})$, and $opt^{*}(P)$ denote the optimal $1$-median costs of $P_{1}$, $P_{2}$, and $P$, repsectively.

We show that $\hat{opt} \leq 3 \cdot opt^{*}(P)$ using the following sequence of inequalities:

\begin{align} \hat{opt} &\leq opt^{*}(P_{1}) + opt^{*}(P_{2}) + n \cdot d(c_{1}^{*},\hat{c}) + n \cdot d(c_{2}^{*},\hat{c}) , \quad \textrm{(using triangle inequality)}\\ &\leq opt^{*}(P) + n \cdot d(c_{1}^{*},\hat{c}) + n \cdot d(c_{2}^{*},\hat{c}) \\ &\leq opt^{*}(P) + n \cdot (d(c_{1}^{*},c^{*}) + d(c_{2}^{*},c^{*})) \quad \textrm{$\because \hat{c}$ is optimal $1$-median for $c_{1}^{*}$ and $c_{2}^{*}$}\\ &\leq opt^{*}(P) + \sum_{x \in P_{1}} (d(x,c_{1}^{*}) + d(x,c^{*})) + \sum_{x \in P_{2}} (d(x,c_{2}^{*}) + d(x,c^{*})), \\ & \quad \quad \textrm{(using triangle inequality)}\\ &= opt^{*}(P) + opt^{*}(P_{1}) + opt^{*}(P_{2}) + opt^{*}(P) \\ &\leq 3 \cdot opt^{*}(P) \end{align}

The above result also holds for the finite metric spaces. Furthermore, for the $1$-means cost function in general metric spaces, you can use the approximate triangle inequality: $d^{2}(a,b) \leq 2 \cdot (d^{2}(a,c) + d^{2}(c,b))$. This will give $\hat{opt} \leq 10 \cdot opt^{*}(P)$

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answer and the link to the paper. $\endgroup$ Oct 8, 2021 at 6:23

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.