Finding a Cluster in Incomplete Data

Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publication30th Annual European Symposium on Algorithms (ESA 2022)
EditorsShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Number of pages14
ISBN (Print)978-3-95977-247-1
Publication statusPublished - 1 Sept 2022

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl -- Leibniz-Zentrum fur Informatik
ISSN (Print)1868-8969
ISSN (Electronic)1868-8969

Cite this