Recently, Bandeira introduced a new type of algorithm (the so-called probably certifiably correct algorithm) that combines fast solvers with the optimality certificates provided by convex relaxations. This talk introduces such an algorithm for the problem of k-means clustering. First, we observe that a certain semidefinite relaxation of k-means is tight with high probability under a certain distribution of planted clusters. Next, we show how to test the optimality of a proposed k-means solution using the relaxation's dual certificate in quasilinear time. (Joint work with Takayuki Iguchi, Jesse Peterson and Soledad Villar.)