<p>Local search (with a single swap) doesn't give you a good approximation factor in the worst case for <span class="math-container">$k$</span>-center, as illustrated by the following example.</p>

<p>Take a simplex in <span class="math-container">$\mathbb{R}^{k-1}$</span>, and put <span class="math-container">$k$</span> points at each of the <span class="math-container">$k$</span> vertices, for a total of <span class="math-container">$k^2$</span> points.</p>

<p>Note that between each pair of vertices of the simplex the distance is 1.  The optimal solution takes one point from each vertex, obtaining cost zero.  And that's the only way to obtain cost zero.. any other type of solution has cost 1.</p>

<p>So if you start local search with <span class="math-container">$C$</span> being any solution that is more than one swap away from such an optimal solution, no local improvement (in one step) is possible.  For example, start local search with <span class="math-container">$C$</span> containing all <span class="math-container">$k$</span> of the points at a single vertex.  That solution has cost 1, and no single swap (or even <span class="math-container">$k-2$</span> swaps) can reduce the cost below 1.</p>

CC BY-SA 4.0
2020-04-25T19:43:44.493Z
2020-04-25T19:43:44.493Z
Neal Young
<p>In the <span class="math-container">$k-$</span>center problem, you're given <span class="math-container">$V$</span> points in Eucledian space, and you're asked to get a subset <span class="math-container">$C\subset V, |C|=k$</span> such that <span class="math-container">$\max _{v\in V}d(v, Closest-Center(C,v))$</span> is minimized. </p>

<p>Now I am aware of the greedy <span class="math-container">$2-$</span>Approximation where you start with a random center, <span class="math-container">$C=\{c_1\}$</span>. Then at each step, add the point furthest from <span class="math-container">$C$</span> iteratively until <span class="math-container">$|C|=k$</span></p>

<p>However, my question is about the local search approach. Namely, start with a set of random <span class="math-container">$k$</span> centers <span class="math-container">$C=\{c_1, ..., c_k\}$</span>, then at each step, for every <span class="math-container">$(c_i, v), \forall v\in V-C, \forall c_i\in C$</span>, check if <span class="math-container">$C-\{c_i\}+\{v\}$</span> improves the cost. There are <span class="math-container">$O(nk)$</span> such pairs, and it takes <span class="math-container">$O(n)$</span> time for each pair to compute it's cost for a total time of <span class="math-container">$O(n^2k)$</span> per iteration. Repeat this until your <span class="math-container">$k$</span> centers don't change after <span class="math-container">$I$</span> iterations (Where <span class="math-container">$I$</span> is trivially <span class="math-container">$O(n^k)$</span> ). </p>

<p>My question is, once the algorithm terminates, does the local search guarantee any approcimation ratio on the maximum distance? Is there any literature on this? I read in a paper that in the <span class="math-container">$k-$</span>median problem, this approach would give a <span class="math-container">$5-$</span>approximation. </p>

CC BY-SA 4.0
2020-04-25T19:32:13.903Z
In your problem specification, what do you mean by "$Closest - Center(C, v)$"?  Doesn't the [standard problem definition](https://en.wikipedia.org/wiki/Metric_k-center) ask to minimize $\max_{v\in V} d(v, C)$?
Neal Young
CC BY-SA 4.0
2020-04-25T19:45:03.793Z
And why do you say *"Repeat this until your $k$ centers don't change after $I$ iterations?"*  If one step (which tries all possible swaps) doesn't give an improvement, then no subsequent step will.  So shouldn't the algorithm just stop after the first step that gives no improvement?
Neal Young
CC BY-SA 4.0
2020-04-26T10:25:32.340Z
@NealYoung By Closest-Center(C,v), I mean a point $c\in C$ that is closest to $v$. This distance is equivalent to $d(v,C)$, this is just a notation difference. Also, I just said that $I$ is trivially $O(n^k)$. It can just as well be $0$ just like you showed. And thank you, you've answered my question!
user3508551
<approximation-algorithms><clustering><search-problem>
Approximation Ratio of Local search for $k-$center problem
user3508551
# Approximation Ratio of Local search for $k-$center problem

(Asked by: username_0 on 2020-04-23)

In the $k-$center problem, you're given $V$ points in Eucledian space, and you're asked to get a subset $C\subset V, |C|=k$ such that $\max \_{v\in V}d(v, Closest-Center(C,v))$ is minimized.

Now I am aware of the greedy $2-$Approximation where you start with a random center, $C=\{c\_1\}$. Then at each step, add the point furthest from $C$ iteratively until $|C|=k$

However, my question is about the local search approach. Namely, start with a set of random $k$ centers $C=\{c\_1, ..., c\_k\}$, then at each step, for every $(c\_i, v), \forall v\in V-C, \forall c\_i\in C$, check if $C-\{c\_i\}+\{v\}$ improves the cost. There are $O(nk)$ such pairs, and it takes $O(n)$ time for each pair to compute it's cost for a total time of $O(n^2k)$ per iteration. Repeat this until your $k$ centers don't change after $I$ iterations (Where $I$ is trivially $O(n^k)$ ).

My question is, once the algorithm terminates, does the local search guarantee any approcimation ratio on the maximum distance? Is there any literature on this? I read in a paper that in the $k-$median problem, this approach would give a $5-$approximation.

**Tags:** approximation-algorithms, clustering, search-problem

> **Comments:**
> **username_1**: In your problem specification, what do you mean by "$Closest - Center(C, v)$"?  Doesn't the [standard problem definition](https://en.wikipedia.org/wiki/Metric_k-center) ask to minimize $\max_{v\in V} d(v, C)$?  
> **username_1**: And why do you say *"Repeat this until your $k$ centers don't change after $I$ iterations?"*  If one step (which tries all possible swaps) doesn't give an improvement, then no subsequent step will.  So shouldn't the algorithm just stop after the first step that gives no improvement?  
> **username_0**: @NealYoung By Closest-Center(C,v), I mean a point $c\in C$ that is closest to $v$. This distance is equivalent to $d(v,C)$, this is just a notation difference. Also, I just said that $I$ is trivially $O(n^k)$. It can just as well be $0$ just like you showed. And thank you, you've answered my question!  

---

## 1 answers

### Answer by username_1 on 2020-04-25. Score: 4 | Accepted answer

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example.

Take a simplex in $\mathbb{R}^{k-1}$, and put $k$ points at each of the $k$ vertices, for a total of $k^2$ points.

Note that between each pair of vertices of the simplex the distance is 1. The optimal solution takes one point from each vertex, obtaining cost zero. And that's the only way to obtain cost zero.. any other type of solution has cost 1.

So if you start local search with $C$ being any solution that is more than one swap away from such an optimal solution, no local improvement (in one step) is possible. For example, start local search with $C$ containing all $k$ of the points at a single vertex. That solution has cost 1, and no single swap (or even $k-2$ swaps) can reduce the cost below 1.


---

