• Exact Exponential Algorithms for Clustering Problems 

      Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Purohit, Nidhi; Saurabh, Saket (Journal article; Peer reviewed, 2022)
      In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric ...
    • 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 ...
    • 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) ...
    • Metric Dimension Parameterized By Treewidth 

      Bonnet, Édouard; Purohit, Nidhi (Journal article; Peer reviewed, 2021)
      A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The METRIC DIMENSION problem asks for a resolving set of minimum size, and in its decision form, ...
    • Multivariate Analysis of Clustering Problems with Constraints 

      Purohit, Nidhi (Doctoral thesis, 2023-12-14)