<p>Suppose <span class="math-container">$\mathcal{P} =\{P_1,\cdots,P_n\}$</span> is a family of <span class="math-container">$n$</span> finite sets in <span class="math-container">$\mathbb{R}^d$</span>. Given set <span class="math-container">$C=\{c_1,\cdots,c_k\}$</span> of <span class="math-container">$k$</span> points, consider the follwoing objective funtion</p>
<p><span class="math-container">$cost(\mathcal{P},C)= \sum_{i=1}^n \min_{c\in C}\max_{p\in P_i}\Vert p-c\Vert$</span>.</p>
<p>Note that when all the sets <span class="math-container">$P_i$</span> are singleton, then this reduces to usual k-median objective. When <span class="math-container">$k=1$</span>, this objective function has the follwing interpretation: Each <span class="math-container">$P_i$</span> is a possible set of clients. Given a facility <span class="math-container">$c$</span>, an adversary chooses to place the client in <span class="math-container">$P_i$</span> farthest from <span class="math-container">$c$</span>, so as to incur maximum cost. So we need to place <span class="math-container">$c$</span> in such a way that this maximum cost is minimized.</p>
<p>Have this problem appeared before? I came up with this problem while reading <a href="https://arxiv.org/pdf/2003.04135.pdf" rel="nofollow noreferrer">Sets Clutering</a>.</p>

CC BY-SA 4.0
2021-06-23T11:39:01.127Z
Can we assume that $C$ comes from some finite set of feasible centers? I mean a discrete version of the problem.
Inuyasha Yagami
CC BY-SA 4.0
2021-06-23T11:44:03.997Z
In the setting of the question, the centers are not from any finte set of feasible centers. Also see https://cstheory.stackexchange.com/questions/48257/hessian-of-non-differentiable-convex-function
Sudipta Roy
<reference-request><approximation-algorithms><clustering>
A variant of k-median clustering
Sudipta Roy
# A variant of k-median clustering

(Asked by: username_0 on 2021-06-23)

Suppose $\mathcal{P} =\{P\_1,\cdots,P\_n\}$ is a family of $n$ finite sets in $\mathbb{R}^d$. Given set $C=\{c\_1,\cdots,c\_k\}$ of $k$ points, consider the follwoing objective funtion

$cost(\mathcal{P},C)= \sum\_{i=1}^n \min\_{c\in C}\max\_{p\in P\_i}\Vert p-c\Vert$.

Note that when all the sets $P\_i$ are singleton, then this reduces to usual k-median objective. When $k=1$, this objective function has the follwing interpretation: Each $P\_i$ is a possible set of clients. Given a facility $c$, an adversary chooses to place the client in $P\_i$ farthest from $c$, so as to incur maximum cost. So we need to place $c$ in such a way that this maximum cost is minimized.

Have this problem appeared before? I came up with this problem while reading [Sets Clutering](https://arxiv.org/pdf/2003.04135.pdf).

**Tags:** reference-request, approximation-algorithms, clustering
> **Comments:**
> **username_1**: Can we assume that $C$ comes from some finite set of feasible centers? I mean a discrete version of the problem.  
> **username_0**: In the setting of the question, the centers are not from any finte set of feasible centers. Also see https://cstheory.stackexchange.com/questions/48257/hessian-of-non-differentiable-convex-function  

---

## 0 answers

