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?
$\begingroup$ The big-O here means the time complexity $\endgroup$– WilliamWNov 12, 2020 at 9:56
Of course not. Otherwise the construction would be "pick an arbitrary set of centers". 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