Finding a Cluster in Incomplete Data

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

doi:10.4230/LIPIcs.ESA.2022.47

Finding a Cluster in Incomplete Data

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	30th Annual European Symposium on Algorithms (ESA 2022)
Editors	Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Pages	47:1-47:14
Number of pages	14
Volume	244
ISBN (Print)	978-3-95977-247-1
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2022.47
Publication status	Published - 1 Sept 2022

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik
Volume	244
ISSN (Print)	1868-8969
ISSN (Electronic)	1868-8969

Access to Document

10.4230/LIPIcs.ESA.2022.47Licence: CC BY

Cite this

Eiben, E., Ganian, R., Kanj, I., Ordyniak, S., & Szeider, S. (2022). Finding a Cluster in Incomplete Data. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (Vol. 244, pp. 47:1-47:14). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 244). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.47

Eiben, Eduard ; Ganian, Robert ; Kanj, Iyad et al. / Finding a Cluster in Incomplete Data. 30th Annual European Symposium on Algorithms (ESA 2022). editor / Shiri Chechik ; Gonzalo Navarro ; Eva Rotenberg ; Grzegorz Herman. Vol. 244 Dagstuhl, Germany : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2022. pp. 47:1-47:14 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{c06bae4bcb754da5bc7dd7d72c419a76,

title = "Finding a Cluster in Incomplete Data",

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.",

author = "Eduard Eiben and Robert Ganian and Iyad Kanj and Sebastian Ordyniak and Stefan Szeider",

year = "2022",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2022.47",

language = "English",

isbn = "978-3-95977-247-1",

volume = "244",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",

pages = "47:1--47:14",

editor = "Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman",

booktitle = "30th Annual European Symposium on Algorithms (ESA 2022)",

}

Eiben, E, Ganian, R, Kanj, I, Ordyniak, S & Szeider, S 2022, Finding a Cluster in Incomplete Data. in S Chechik, G Navarro, E Rotenberg & G Herman (eds), 30th Annual European Symposium on Algorithms (ESA 2022). vol. 244, Leibniz International Proceedings in Informatics (LIPIcs), vol. 244, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 47:1-47:14. https://doi.org/10.4230/LIPIcs.ESA.2022.47

Finding a Cluster in Incomplete Data. / Eiben, Eduard; Ganian, Robert; Kanj, Iyad et al.
30th Annual European Symposium on Algorithms (ESA 2022). ed. / Shiri Chechik; Gonzalo Navarro; Eva Rotenberg; Grzegorz Herman. Vol. 244 Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2022. p. 47:1-47:14 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 244).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Finding a Cluster in Incomplete Data

AU - Eiben, Eduard

AU - Ganian, Robert

AU - Kanj, Iyad

AU - Ordyniak, Sebastian

AU - Szeider, Stefan

PY - 2022/9/1

Y1 - 2022/9/1

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.ESA.2022.47

DO - 10.4230/LIPIcs.ESA.2022.47

M3 - Conference contribution

SN - 978-3-95977-247-1

VL - 244

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 47:1-47:14

BT - 30th Annual European Symposium on Algorithms (ESA 2022)

A2 - Chechik, Shiri

A2 - Navarro, Gonzalo

A2 - Rotenberg, Eva

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

CY - Dagstuhl, Germany

ER -

Eiben E, Ganian R, Kanj I, Ordyniak S, Szeider S. Finding a Cluster in Incomplete Data. In Chechik S, Navarro G, Rotenberg E, Herman G, editors, 30th Annual European Symposium on Algorithms (ESA 2022). Vol. 244. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. 2022. p. 47:1-47:14. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ESA.2022.47