New answers tagged clustering
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
Related Tags
clustering × 145algorithms × 53
machine-learning × 30
graphs × 27
data-mining × 19
optimization × 14
parallel-computing × 5
statistics × 5
python × 5
complexity-theory × 4
trees × 4
computational-geometry × 4
strings × 4
weighted-graphs × 4
classification × 4
partitions × 4
time-complexity × 3
algorithm-analysis × 3
data-structures × 2
reductions × 2
sorting × 2
np-hard × 2
approximation × 2
neural-networks × 2
sets × 2