1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ The big-O here means the time complexity $\endgroup$
    – WilliamW
    Nov 12, 2020 at 9:56

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.