# A variant of k-median clustering

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.

• Can we assume that $C$ comes from some finite set of feasible centers? I mean a discrete version of the problem. Jun 23, 2021 at 11:39
• In the setting of the question, the centers are not from any finte set of feasible centers. Also see cstheory.stackexchange.com/questions/48257/… Jun 23, 2021 at 11:44