answer all reasoning according to Algorithmic properties of the k-means problem

1) NP-hard if the dimensionality of the data is at least 2 (d>=2). (how?)

2) Finding the best solution in polynomial time is infeasible. (Really?)

3) For d=1 the problem is solvable in polynomial time (how?)

4) A simple iterative algorithm works quite well in practice