# Approximation Ratio of Local search for $k-$center problem

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.

• In your problem specification, what do you mean by "$Closest - Center(C, v)$"? Doesn't the standard problem definition ask to minimize $\max_{v\in V} d(v, C)$? Apr 25, 2020 at 19:32
• 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? Apr 25, 2020 at 19:45
• @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! Apr 26, 2020 at 10:25

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.
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.