RECORD
The Parameterized Complexity of Clustering Incomplete Data
Data Structures and Algorithms · Submitted 4 Nov 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study fundamental clustering problems for incomplete data. | contribution 0.56 | 0.83 | 0.03 | asserted 0.83 |
| s1 | 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. | background 0.88 | 0.15 | 0.03 | asserted 0.88 |
| s2 | 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. | contribution 0.78 | 0.95 | 0.32 | asserted 1.00 |
| s3 | 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. | result 0.99 | 0.96 | 0.74 | asserted 1.00 |
| s4 | A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k+r. | result 0.92 | 0.93 | 0.10 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
How the literature uses it
2 arXiv papers cite this in 12 sentences
Papers citing it · 6 sentences without a confident label
Compares with it 1 paper
-
While the focus of the previous works [ref] is on parameterized complexity studies, in this work we settle very basic questions on the DMC problem, relying on several combinatorial insights, including results from (extremal) combinatorics (most prominently, Deza's theorem [ref] ).
The Complexity of Binary Matrix Completion Under Diameter Constraints · Introduction · 0.84
Cites it as background 1 paper
-
Eiben et al. [ref] investigated clustering problems where one wants to partition the rows of the completed matrix into a given number of clusters of small radius or of small diameter.
The Complexity of Binary Matrix Completion Under Diameter Constraints · Introduction · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.