10 citations · 33 across the 24 of their papers we have counts for
20 papers · 1 filter
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +4
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most weights can be changed to form a metric. Motivated by metric…
Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
Sina Bagheri Nezhad, Sayan Bandyapadhyay, Tianzhi Chen
In a seminal work, Chierichetti et al. introduced the -fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called…
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
A Polynomial-Time Approximation for Pairwise Fair -Median Clustering
Sayan Bandyapadhyay, Eden Chlamtáč, Zachary Friggstad +3
In this work, we study pairwise fair clustering with groups, where for every cluster and every group , the number of points in from group mus…
On Colorful Vertex and Edge Cover Problems
Sayan Bandyapadhyay, Aritra Banik, Sujoy Bhore
In this paper, we study two generalizations of Vertex Cover and Edge Cover, namely Colorful Vertex Cover and Colorful Edge Cover. In the Colorful Vertex Cover problem, given an …
FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
Sayan Bandyapadhyay, William Lochet, Saket Saurabh
Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approx…
Proportionally Fair Matching with Multiple Groups
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar +1
The study of fair algorithms has become mainstream in machine learning and artificial intelligence due to its increasing demand in dealing with biases and discrimination. Along thi…
Parameterized Approximation Algorithms for -Center Clustering and Variants
Sayan Bandyapadhyay, Zachary Friggstad, Ramin Mousavi
-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approxi…
How to Find a Good Explanation for Clustering?
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +3
-means and -median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpr…
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +2
We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on -minor free graphs. In particular, we obtain the following resul…
Lossy Kernelization of Same-Size Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +2
In this work, we study the -median clustering problem with an additional equal-size constraint on the clusters, from the perspective of parameterized preprocessing. Our main res…
Parameterized Complexity of Feature Selection for Categorical Data Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +1
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 approa…
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
Sayan Bandyapadhyay, Fedor V. Fomin, Kirill Simonov
Fair clustering is a constrained variant of clustering where the goal is to partition a set of colored points, such that the fraction of points of any color in every cluster is mor…
Approximate Covering with Lower and Upper Bounds via LP Rounding
Sayan Bandyapadhyay, Aniket Basu Roy
In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set of points, a collection of balls, and parameters and…
Improved Bounds for Metric Capacitated Covering Problems
Sayan Bandyapadhyay
In the Metric Capacitated Covering (MCC) problem, given a set of balls in a metric space with metric and a capacity parameter , the goal is to find a minim…
On Perturbation Resilience of Non-Uniform -Center
Sayan Bandyapadhyay
The Non-Uniform -center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical -center clusteri…
A Constant Approximation for Colorful k-Center
Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai +1
In this paper, we consider the colorful -center problem, which is a generalization of the well-known -center problem. Here, we are given red and blue points in a metric space…
Capacitated Covering Problems in Geometric Spaces
Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar +1
In this article, we consider the following capacitated covering problem. We are given a set of points and a set of balls from some metric space, and a positiv…
A Variant of the Maximum Weight Independent Set Problem
Sayan Bandyapadhyay
We study a natural extension of the Maximum Weight Independent Set Problem (MWIS), one of the most studied optimization problems in Graph algorithms. We are given a graph …
Voronoi Game on Graphs
Sayan Bandyapadhyay, Aritra Banik, Sandip Das +1
\textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a giv…