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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.