Browsing Department of Informatics by Author "Bandyapadhyay, Sayan"

Now showing items 1-6 of 6

    • FPT Approximation for Fair Minimum-Load Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2022)
      In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ...

    • Geometric Planar Networks on Bichromatic Points 

      Bandyapadhyay, Sayan; Banik, Aritra; Bhore, Sujoy; Nollenburg, Martin (Journal article; Peer reviewed, 2020)
      We study four classical graph problems – Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic ( Open image in new window and Open image in new ...

    • How to find a good explanation for clustering? 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, ...

    • Lossy Kernelization of Same-Size Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) ...

    • On Perturbation Resilience of Non-uniform k-Center 

      Bandyapadhyay, Sayan (Journal article; Peer reviewed, 2021)
      The Non-Uniform k-center (NUkC) problem has recently been formulated by Chakrabarty et al. [ICALP, 2016; ACM Trans Algorithms 16(4):46:1–46:19, 2020] as a generalization of the classical k-center clustering problem. In ...

    • Parameterized Complexity of Feature Selection for Categorical Data Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2021)
      We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, ...