All Questions
Tagged with clustering optimization
4 questions
3
votes
2
answers
175
views
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes.
Does this have a constant approximation?
($p,k$ and the graph are all part of the ...
- 228
5
votes
0
answers
162
views
Exact algorithms for $k$-means
Lets recall the definition of $k$-means clustering for euclidean spaces.
Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $...
- 319
3
votes
1
answer
96
views
Centroid in $\ell_2$ distance
Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$
- 791
1
vote
0
answers
538
views
Time complexity of clustering based on random walk
What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph?
Can I use the complexity of eigen vector computation for this purpose?
The ...
- 11