  We study fundamental clustering problems for incomplete data. Specifically,
given a set of incomplete d-dimensional vectors (representing rows of a
matrix), the goal is to complete the missing vector entries in a way that
admits a partitioning of the vectors into at most $k$ clusters with radius or
diameter at most r. We give tight characterizations of the parameterized
complexity of these problems with respect to the parameters k, r, and the
minimum number of rows and columns needed to cover all the missing entries. We
show that the considered problems are fixed-parameter tractable when
parameterized by the three parameters combined, and that dropping any of the
three parameters results in parameterized intractability. A byproduct of our
results is that, for the complete data setting, all problems under
consideration are fixed-parameter tractable parameterized by k+r.
