The k-center cost function. An alternative to k-means is the k-center clustering problem, defined as follows:...

Transcribed Image Text:

The k-center cost function. An alternative to k-means is the k-center clustering problem, defined as follows: Input: Data points x,...,xn in some metric space (X, d); integer k > 0 Output: "Centers" ,..., Mk E X Goal: Minimize max min d(xi, Hj). i 1 (b) Suppose we run farthest-first traversal on this data set, starting with = H will it pick as 2 and ? What is the k-center cost of this solution? Which centers Interestingly, farthest-first traversal is guaranteed to return a solution whose k-center cost is at most twice the cost of the best solution. The k-center cost function. An alternative to k-means is the k-center clustering problem, defined as follows: Input: Data points x,...,xn in some metric space (X, d); integer k > 0 Output: "Centers" ,..., Mk E X Goal: Minimize max min d(xi, Hj). i 1 (b) Suppose we run farthest-first traversal on this data set, starting with = H will it pick as 2 and ? What is the k-center cost of this solution? Which centers Interestingly, farthest-first traversal is guaranteed to return a solution whose k-center cost is at most twice the cost of the best solution.