<div class="csl-bib-body">
<div class="csl-entry">Eiben, E., Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2022). Finding a Cluster in Incomplete Data. In <i>30th Annual European Symposium on Algorithms (ESA 2022)</i> (pp. 1–14). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.47</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/150281
-
dc.description.abstract
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
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
clustering
en
dc.subject
incomplete data
en
dc.subject
parameterized complexity
en
dc.title
Finding a Cluster in Incomplete Data
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.contributor.affiliation
University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
DePaul University, United States of America (the)
-
dc.contributor.affiliation
University of Leeds, United Kingdom of Great Britain and Northern Ireland (the)
