Our results fit into a line of prior work on approximating the cost of optimization problems without necessarily computing an optimal solution. These have been investigated before for various problems and in various contexts, including estimating minimum spanning tree [1]}, [2]}, [3]}, minimum cost matchings and Earth Mover's Distance [1]}, [5]}, [6]}, [7]}, minimum vertex cover and maximum matching [8]}, [9]}, [10]}, [11]}, [12]}, [13]}, [14]} and model-fit [15]}, [16]}, [17]}. Specifically for clustering problems, the value of the clustering cost is an important statistic; used, for example, in the “elbow method” for determining the number of clusters needed. We will show these sketches may be efficiently maintained on a stream as well as for distributed-memory models, implying \((nd)\) -bit algorithms for these models of computation.
