New answers tagged

4

The first event at time $t_0$ needs to be in a bucket. We can safely choose the bucket $[t_0, t_0+30]$, as there is nothing to gain by making it start earlier. We then move on to the next event starting at $t>t_0+30$ (earlier events fall into the bucket we chose). We once again choose the latest bucket containing that event. It is not hard to prove that ...


0

I think this should be possible using the scikit-learn implementation; see here: https://stackoverflow.com/questions/38355153/initial-centroids-for-scikit-learn-kmeans-clustering.


2

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


Top 50 recent answers are included