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.

翻译：具体地说,考虑到一组不完整的二维矢量(代表一个矩阵的行),目标是完成缺失的矢量条目,允许将矢量分解成最多为1美元、半径或直径最多为r的矢量集群。我们对这些参数k、r和覆盖所有缺失条目所需的最小行数和列数的参数复杂性作了严格描述。我们表明,在结合三个参数参数参数参数参数时,所考虑的问题是可以固定的参数可移动的,而放弃任何三个参数都会导致参数的吸引力。我们结果的一个副产品是,对于完整的数据设置,所考虑的所有问题都由 k+r 固定的参数可移动的参数。