<p>Let <span class="math-container">$opt^{*}(P_{1})$</span>, <span class="math-container">$opt^{*}(P_{2})$</span>, and <span class="math-container">$opt^{*}(P)$</span> denote the optimal <span class="math-container">$1$</span>-median costs of <span class="math-container">$P_{1}$</span>, <span class="math-container">$P_{2}$</span>, and <span class="math-container">$P$</span>, repsectively.</p>
<p>We show that <span class="math-container">$\hat{opt} \leq 3 \cdot opt^{*}(P)$</span> using the following sequence of inequalities:</p>
<p><span class="math-container">\begin{align}
\hat{opt} &amp;\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)}\\
&amp;\leq opt^{*}(P) + n \cdot d(c_{1}^{*},\hat{c}) + n \cdot d(c_{2}^{*},\hat{c}) \\
&amp;\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}^{*}$}\\ 
&amp;\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^{*})), \\ &amp; \quad \quad \textrm{(using triangle inequality)}\\
&amp;= opt^{*}(P) + opt^{*}(P_{1}) + opt^{*}(P_{2}) + opt^{*}(P) \\
&amp;\leq 3 \cdot opt^{*}(P)
\end{align}</span></p>
<p>The above result also holds for the finite metric spaces. Furthermore, for the <span class="math-container">$1$</span>-means cost function in general metric spaces, you can use the approximate triangle inequality: <span class="math-container">$d^{2}(a,b) \leq 2 \cdot (d^{2}(a,c) + d^{2}(c,b))$</span>. This will give <span class="math-container">$\hat{opt} \leq 10 \cdot opt^{*}(P)$</span></p>

CC BY-SA 4.0
2021-10-08T06:23:36.937Z
Thanks for the answer and the link to the paper.
Sudipta Roy
CC BY-SA 4.0
2021-10-05T20:11:21.710Z
2021-10-05T20:32:14.077Z
2021-10-05T20:32:14.077Z
Inuyasha Yagami
<p>Let <span class="math-container">$P_1$</span> and <span class="math-container">$P_2$</span> be two disjoint point sets in <span class="math-container">$\mathbb{R}^d$</span> and <span class="math-container">$n = \vert P_1\vert = \vert P_2\vert$</span> and <span class="math-container">$P = P_1\cup P_2$</span>. Let <span class="math-container">$c^\star$</span> be the optimal 1-median for <span class="math-container">$P$</span> and <span class="math-container">$opt^\star$</span> is the cost of assigning all points of <span class="math-container">$P$</span> to <span class="math-container">$c^\star$</span>(the sum of the distances of all points of <span class="math-container">$P$</span> to <span class="math-container">$c^\star$</span>).</p>
<p>For <span class="math-container">$j\in \{1,2\}$</span>, let <span class="math-container">$c_j^\star$</span> is the optimal 1-median of <span class="math-container">$P_j^\star$</span> and and let <span class="math-container">$\hat{c}$</span> is the optimal 1-median of the 2-point set <span class="math-container">$\{c_1^\star,c_2^\star\}$</span>. Let <span class="math-container">$\hat{opt}$</span> be the cost of assigning all point of <span class="math-container">$P$</span> to <span class="math-container">$\hat{c}$</span>.</p>
<p>My question is that</p>
<ol>
<li>Does the ratio <span class="math-container">$\frac{\hat{opt}}{opt^\star}$</span> is bounded from above by some quantity or there exists &quot;bad&quot; instances (perhaps low dimensional) where it is lower bounded? (My guess is that the latter is true)</li>
<li>What is the situation for finite metric spaces?</li>
<li>What about the &quot;means&quot; or the centroid?</li>
</ol>
<p>The obvious motivation for the question is that if the &quot;divide and conquer&quot; 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.</p>

CC BY-SA 4.0
2021-10-05T16:07:30.890Z
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$?
Neal Young
CC BY-SA 4.0
2021-10-05T16:16:52.057Z
@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.
Sudipta Roy
CC BY-SA 4.0
2021-10-05T20:30:09.350Z
@SudiptaRoy This technique is used in general to design streaming algorithms for the $k$-median/means problem. You may want to see [this](http://www.cs.columbia.edu/~rjaiswal/ajmNIPS09.pdf) paper: Algorithm 3 on Page 5.
Inuyasha Yagami
<ds.algorithms><lower-bounds><clustering>
Divide and Conquer Algorithm for 1-Median Problem
Sudipta Roy
# Divide and Conquer Algorithm for 1-Median Problem

(Asked by: username_0 on 2021-10-05)

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.

**Tags:** ds.algorithms, lower-bounds, clustering

> **Comments:**
> **username_1**: 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$?  
> **username_0**: @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.  
> **username_2**: @SudiptaRoy This technique is used in general to design streaming algorithms for the $k$-median/means problem. You may want to see [this](http://www.cs.columbia.edu/~rjaiswal/ajmNIPS09.pdf) paper: Algorithm 3 on Page 5.  

---

## 1 answers

### Answer by username_2 on 2021-10-05. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks for the answer and the link to the paper.  

---

