Timezone: »

 
Poster
The Complexity of k-Means Clustering when Little is Known
Robert Ganian · Thekla Hamm · Viktoriia Korchemna · Karolina Okrasa · Kirill Simonov

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #1207
in Poster Session 3 »

In the area of data analysis and arguably even in machine learning as a whole, few approaches have been as impactful as the classical k-means clustering. Here, we study the complexity of k-means clustering in settings where most of the data is not known or simply irrelevant. To obtain a more fine-grained understanding of the tractability of this clustering problem, we apply the parameterized complexity paradigm and obtain three new algorithms for k-means clustering of incomplete data: one for the clustering of bounded-domain (i.e., integer) data, and two incomparable algorithms that target real-valued data. Our approach is based on exploiting structural properties of a graphical encoding of the missing entries, and we show that tractability can be achieved using significantly less restrictive parameterizations than in the complementary case of few missing entries.

Keywords: OPT: Discrete and Combinatorial Optimization · T: Everything Else · T: Optimization

Author Information

Robert Ganian (TU Wien)
Thekla Hamm (TU Wien)
Viktoriia Korchemna (TU Wien)
Karolina Okrasa (University of Warsaw)
Kirill Simonov (University of Bergen)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors