<p>I have not verified the forward direction. However, here is a counterexample for reverse direction: <span class="math-container">$\mathcal{P} = \{ P_1, P_2,P_3\}$</span>, where <span class="math-container">$P_{1} = \{(-1,0)\}$</span>, <span class="math-container">$P_{2} = \{(1,0)\}$</span>, and <span class="math-container">$P_{3} = \{(0,1),(0,-1)\}$</span>. Here <span class="math-container">$c^{*} = (0,0)$</span>. However, <span class="math-container">$p_{1}^{*} = (-1,0)$</span>, <span class="math-container">$p_{2}^{*} = (1,0)$</span>, and <span class="math-container">$p_{3}^{*} = (0,1)$</span> or <span class="math-container">$(0,-1)$</span> that have mean either <span class="math-container">$(0,1/3)$</span> or <span class="math-container">$(0,-1/3)$</span></p>

CC BY-SA 4.0
2021-12-02T15:17:14.453Z
Why is origin is the optimal center?
Sudipta Roy
CC BY-SA 4.0
2021-12-02T15:28:36.607Z
@SudiptaRoy Let $(a,b)$ be the center. Then, the cost is $(a-1)^2 + (a+1)^2 + 2b^2 + \max\{a^2+(b-1)^2, a^2+(b+1)^2\}$. Solve it. The function is minimized at the origin.
Inuyasha Yagami
CC BY-SA 4.0
2021-12-02T15:31:12.147Z
After my reply, I was thinking about this approach. Thank you
Sudipta Roy
CC BY-SA 4.0
2021-12-01T16:53:50.727Z
2021-12-01T16:53:50.727Z
Inuyasha Yagami
<p>Let <span class="math-container">$\mathcal{P} = \{P_1, \cdots,P_n\}$</span> be a family of finite point sets in <span class="math-container">$\mathbb{R}^d$</span>, each having at most <span class="math-container">$m$</span> points. Consider the following objective function</p>
<p><span class="math-container">\begin{align}
cost(\mathcal{P},c) = \sum_{i\in[n]}\max_{p\in P_i}\Vert p-c\Vert^2
\end{align}</span></p>
<p>Let <span class="math-container">$c^\star$</span> be the point which minimizes the above objective function and the optimal cost is <span class="math-container">$opt(\mathcal{P}) = cost(\mathcal{P},c^\star)$</span>.</p>
<p>For a point <span class="math-container">$c\in\mathbb{R}^d$</span> and <span class="math-container">$i \in [n]$</span>, let <span class="math-container">$p_i^{(c)}$</span> be the point of <span class="math-container">$P_i$</span> farthest from <span class="math-container">$c$</span>, i.,e.
<span class="math-container">\begin{align*}
    \Vert p_i^{(c)} -c\Vert^2 = \max_{p\in P_i}\Vert p-c\Vert^2
\end{align*}</span>
Define <span class="math-container">$c$</span>-mean to be the mean of these farthest points
<span class="math-container">\begin{align*}
    \mu^{(c)} = \frac{1}{n}\sum_{i=1}^n p_i^{(c)}
\end{align*}</span></p>
<p>So we have
<span class="math-container">\begin{align*}
    cost_2(\mathcal{P},c) = \sum_{i=1}^n \Vert p_i^{(c)} -c\Vert^2
\end{align*}</span>
For ease of notation, let <span class="math-container">$p_i^\star = p_i^{(c^\star)}$</span> and <span class="math-container">$\mu^\star = \mu^{(c^\star)}$</span>. So
<span class="math-container">\begin{align*}
    opt_2(\mathcal{P}) = \sum_{i=1}^n \Vert p_i^\star - c^\star\Vert^2
\end{align*}</span></p>
<p>Note that if every set in <span class="math-container">$\mathcal{P}$</span> is singleton, then this is the well-known <span class="math-container">$k$</span>-means objective and <span class="math-container">$c^\star = \mu^\star$</span>.</p>
<p>It is easy to show the following, for any <span class="math-container">$c\in \mathbb{R}^d$</span>
<span class="math-container">\begin{align}
cost(\mathcal{P},c) \leq opt(\mathcal{P}) + n\Vert c - \mu^{(c)}\Vert^2
\end{align}</span></p>
<p>It follows that if there is a point <span class="math-container">$c$</span> such that <span class="math-container">$c = \mu^{(c)}$</span>, then <span class="math-container">$c$</span> is <em>an</em> optimum center. This already helps to find the optimal solution in some simple scenarios, such as <span class="math-container">$\mathcal{P} = \{P_1,P_2\}$</span>, where <span class="math-container">$P_1=\{(1,1),(1,-1)\}$</span> and <span class="math-container">$P_2=\{(-1,1),(-1-1)\}$</span>. <strong>However</strong> it seems to me that the reverse direction may not hold: meaning for any optimal center <span class="math-container">$c^\star$</span>, it may not be the case that <span class="math-container">$c^\star = \mu^{(c^\star)}$</span>. So far I have not been able to come up with a counter example.</p>
<p>Does anyone have some idea as to finding a counter example.</p>
<p>P.s. Is this objective function already known?</p>

CC BY-SA 4.0
2021-12-01T17:16:44.540Z
Yes, this objective function is known. Check Definition 1.1. of this [paper](https://arxiv.org/pdf/2111.04804.pdf). Yours is a special case for $k = 1$, $p = \infty$, and $q = 1$.
Inuyasha Yagami
CC BY-SA 4.0
2021-12-02T03:33:09.670Z
@InuyashaYagami thanks for the reference. I have seen this paper but did not read it.
Sudipta Roy
<reference-request><approximation-algorithms><computational-geometry><clustering>
A counter example for the set mean objective
Sudipta Roy
# A counter example for the set mean objective

(Asked by: username_0 on 2021-12-01)

Let $\mathcal{P} = \{P\_1, \cdots,P\_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function

\begin{align}
cost(\mathcal{P},c) = \sum\_{i\in[n]}\max\_{p\in P\_i}\Vert p-c\Vert^2
\end{align}

Let $c^\star$ be the point which minimizes the above objective function and the optimal cost is $opt(\mathcal{P}) = cost(\mathcal{P},c^\star)$.

For a point $c\in\mathbb{R}^d$ and $i \in [n]$, let $p\_i^{(c)}$ be the point of $P\_i$ farthest from $c$, i.,e.
\begin{align\*}
\Vert p\_i^{(c)} -c\Vert^2 = \max\_{p\in P\_i}\Vert p-c\Vert^2
\end{align\*}
Define $c$-mean to be the mean of these farthest points
\begin{align\*}
\mu^{(c)} = \frac{1}{n}\sum\_{i=1}^n p\_i^{(c)}
\end{align\*}

So we have
\begin{align\*}
cost\_2(\mathcal{P},c) = \sum\_{i=1}^n \Vert p\_i^{(c)} -c\Vert^2
\end{align\*}
For ease of notation, let $p\_i^\star = p\_i^{(c^\star)}$ and $\mu^\star = \mu^{(c^\star)}$. So
\begin{align\*}
opt\_2(\mathcal{P}) = \sum\_{i=1}^n \Vert p\_i^\star - c^\star\Vert^2
\end{align\*}

Note that if every set in $\mathcal{P}$ is singleton, then this is the well-known $k$-means objective and $c^\star = \mu^\star$.

It is easy to show the following, for any $c\in \mathbb{R}^d$
\begin{align}
cost(\mathcal{P},c) \leq opt(\mathcal{P}) + n\Vert c - \mu^{(c)}\Vert^2
\end{align}

It follows that if there is a point $c$ such that $c = \mu^{(c)}$, then $c$ is *an* optimum center. This already helps to find the optimal solution in some simple scenarios, such as $\mathcal{P} = \{P\_1,P\_2\}$, where $P\_1=\{(1,1),(1,-1)\}$ and $P\_2=\{(-1,1),(-1-1)\}$. **However** it seems to me that the reverse direction may not hold: meaning for any optimal center $c^\star$, it may not be the case that $c^\star = \mu^{(c^\star)}$. So far I have not been able to come up with a counter example.

Does anyone have some idea as to finding a counter example.

P.s. Is this objective function already known?

**Tags:** reference-request, approximation-algorithms, computational-geometry, clustering
> **Comments:**
> **username_1**: Yes, this objective function is known. Check Definition 1.1. of this [paper](https://arxiv.org/pdf/2111.04804.pdf). Yours is a special case for $k = 1$, $p = \infty$, and $q = 1$.  
> **username_0**: @InuyashaYagami thanks for the reference. I have seen this paper but did not read it.  

---

## 1 answers

### Answer by username_1 on 2021-12-01. Score: 0 | Accepted answer

I have not verified the forward direction. However, here is a counterexample for reverse direction: $\mathcal{P} = \{ P\_1, P\_2,P\_3\}$, where $P\_{1} = \{(-1,0)\}$, $P\_{2} = \{(1,0)\}$, and $P\_{3} = \{(0,1),(0,-1)\}$. Here $c^{\*} = (0,0)$. However, $p\_{1}^{\*} = (-1,0)$, $p\_{2}^{\*} = (1,0)$, and $p\_{3}^{\*} = (0,1)$ or $(0,-1)$ that have mean either $(0,1/3)$ or $(0,-1/3)$

> **Comments:**
> **username_0**: Why is origin is the optimal center?  
> **username_1**: @SudiptaRoy Let $(a,b)$ be the center. Then, the cost is $(a-1)^2 + (a+1)^2 + 2b^2 + \max\{a^2+(b-1)^2, a^2+(b+1)^2\}$. Solve it. The function is minimized at the origin.  
> **username_0**: After my reply, I was thinking about this approach. Thank you  

---

