Question in coreset construction fro K-median clustering I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $[α, β]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$. I am wondering if the construction still work if $A$ is an arbitrary set of $αk$ centers?
Can anyone help prove the correctness of my suggestion?
Of course not. Otherwise the construction would be &quot;pick an arbitrary set of centers&quot;.
You can follows the proof and see that the size of the coreset depends polynomially on $\beta$ and $\alpha$.
If they are $O(1)$ they can be hidden in the $O()$ notation. Otherwise, someone needs to  pay.  See more details in Section 6 here:
https://arxiv.org/abs/2011.09384