Eiben, E., Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2022). Finding a Cluster in Incomplete Data. In 30th Annual European Symposium on Algorithms (ESA 2022) (pp. 1–14). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.47
We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete d-dimensional vectors over the binary domain and integers k and r, and the goal is to complete the missing vector entries so that the multiset of complete vectors either contains (i) a cluster of k vectors of radius at most r, or (ii) a cluster of k vectors of diameter at most r. We give tight characterizations of the parameterized complexity of the problems under consideration with respect to the parameters k, r, and a third parameter that captures the missing vector entries.
en
Project title:
Parameterisierte Analyse in der Künstlichen Intelligenz: Y1329-N (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) SAT-Basierende lokale Verbesserungsmethoden: P32441-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
-
Project (external):
Engineering and Physical Sciences Research Council (EPSRC) Vienna Science and Technology Fund (WWTF)
CC BY 4.0
