<p>The <span class="math-container">$k$</span>-clustering problem is defined as follows: Given a set <span class="math-container">$C$</span> of clients and a set <span class="math-container">$L$</span> of facility locations defined over a distance metric <span class="math-container">$d$</span>. Open a set <span class="math-container">$F$</span> of <span class="math-container">$k$</span> facility in <span class="math-container">$L$</span> such that the total cost of assigning the clients to their closest facilities is minimized, i.e.,</p>
<p><span class="math-container">$$\text{minimize} \quad \Phi_{p}(F) \equiv \left( \sum_{j = 1}^{|C|} \, d(j,F)^{p} \right)^{1/p}, \quad \quad \text{where } d(j,F) = \min_{f \in F} \big\{ d(j,f) \big\}$$</span></p>
<p>For the <span class="math-container">$k$</span>-median problem <span class="math-container">$p = 1$</span>; for the <span class="math-container">$k$</span>-means problem <span class="math-container">$p = 2$</span>; and for the <span class="math-container">$k$</span>-center problem <span class="math-container">$p = \infty$</span>. I agree with all these definitions.</p>
<p>However, in the abstract of <a href="https://arxiv.org/pdf/0809.2554.pdf" rel="nofollow noreferrer">this</a> paper, the authors say that a <span class="math-container">$O(p)$</span>-approximation for the <span class="math-container">$k$</span>-clustering problem gives <span class="math-container">$O(\log n)$</span> approximation for the <span class="math-container">$k$</span>-center problem. I could not understand this. On page 8, they also state the following statement:</p>
<blockquote>
<p>The
implication for <span class="math-container">$k$</span>-center follows from the fact that for vectors of length <span class="math-container">$n$</span>, the norm <span class="math-container">$\|.\|_{\infty}$</span> is within a
constant factor of the norm <span class="math-container">$\|.\|_{\log n}$</span>, and hence <span class="math-container">$\max_{j \in C} d(j, F)$</span> is within a constant factor of <span class="math-container">$\Phi_{\log n}(F)$</span>.</p>
</blockquote>
<p>I could not prove this fact. Can somebody please provide some hint/reference for the same? Thank You.</p>

CC BY-SA 4.0
2021-07-05T02:31:04.000Z
Sorry if I'm missing something obvious, but isn't the $p$-norm statement just that in $\mathbb{R}^n$, $\|\mathbf{x}\|_{\infty}\leq \|\mathbf{x}\|_{\log n}\leq (n\|\mathbf{x}\|^{\log n}_{\infty})^{1/\log n}\leq e\|\mathbf{x}\|_{\infty}$. The abstract says they give a $O(p)$ approximation for the $\ell_p$ norm for any $p$, which is degenerate for $p=\infty$, but this computation shows you can use it for $p=\log n$ to get a $O(\log n)$ approximation for the $k$-center problem.
Jason Gaitonde
CC BY-SA 4.0
2021-07-05T04:48:17.740Z
@J.G Yup. You are absolutely right! I completely missed that. It answers my question. Thanks!
Inuyasha Yagami
CC BY-SA 4.0
2021-07-06T17:13:01.693Z
glad to have helped!
Jason Gaitonde
<clustering>
How general cost function for $p = \log n$ is the $k$-center cost function?
Inuyasha Yagami
# How general cost function for $p = \log n$ is the $k$-center cost function?

(Asked by: username_0 on 2021-07-04)

The $k$-clustering problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the total cost of assigning the clients to their closest facilities is minimized, i.e.,

$$\text{minimize} \quad \Phi\_{p}(F) \equiv \left( \sum\_{j = 1}^{|C|} \, d(j,F)^{p} \right)^{1/p}, \quad \quad \text{where } d(j,F) = \min\_{f \in F} \big\{ d(j,f) \big\}$$

For the $k$-median problem $p = 1$; for the $k$-means problem $p = 2$; and for the $k$-center problem $p = \infty$. I agree with all these definitions.

However, in the abstract of [this](https://arxiv.org/pdf/0809.2554.pdf) paper, the authors say that a $O(p)$-approximation for the $k$-clustering problem gives $O(\log n)$ approximation for the $k$-center problem. I could not understand this. On page 8, they also state the following statement:

> The
> implication for $k$-center follows from the fact that for vectors of length $n$, the norm $\|.\|\_{\infty}$ is within a
> constant factor of the norm $\|.\|\_{\log n}$, and hence $\max\_{j \in C} d(j, F)$ is within a constant factor of $\Phi\_{\log n}(F)$.

I could not prove this fact. Can somebody please provide some hint/reference for the same? Thank You.

**Tags:** clustering
> **Comments:**
> **username_1**: Sorry if I'm missing something obvious, but isn't the $p$-norm statement just that in $\mathbb{R}^n$, $\|\mathbf{x}\|_{\infty}\leq \|\mathbf{x}\|_{\log n}\leq (n\|\mathbf{x}\|^{\log n}_{\infty})^{1/\log n}\leq e\|\mathbf{x}\|_{\infty}$. The abstract says they give a $O(p)$ approximation for the $\ell_p$ norm for any $p$, which is degenerate for $p=\infty$, but this computation shows you can use it for $p=\log n$ to get a $O(\log n)$ approximation for the $k$-center problem.  
> **username_0**: @J.G Yup. You are absolutely right! I completely missed that. It answers my question. Thanks!  
> **username_1**: glad to have helped!  

---

## 0 answers

