Article ID Journal Published Year Pages File Type
10331867 Information Processing Letters 2015 4 Pages PDF
Abstract
We give an improved analysis of the simple D2-sampling based PTAS for the k-means clustering problem given by Jaiswal et al. [3]. The improvement on the running time is from O(nd⋅2O˜(k2/ϵ)) to O(nd⋅2O˜(k/ϵ)).
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Improved analysis of D2-sampling based PTAS for k-means and other clustering problems
Authors
, , ,