10 citations · 33 across the 24 of their papers we have counts for
38 papers
FPTAS for Polygonal Multi-Robot Motion Planning
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain with vertices and…
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…
Extraction Theorems With Small Extraction Numbers
Arjun Agarwal, Sayan Bandyapadhyay
In this work, we develop Extraction Theorems for classes of geometric objects with small extraction numbers. These classes include intervals, axis-parallel segments, axis-parallel…
Fair Summarization: Bridging Quality and Diversity in Extractive Summaries
Sina Bagheri Nezhad, Sayan Bandyapadhyay, Ameeta Agrawal
Fairness in multi-document summarization of user-generated content remains a critical challenge in natural language processing (NLP). Existing summarization methods often fail to e…
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…
An -Time Approximation Scheme for Geometric Many-to-Many Matching
Sayan Bandyapadhyay, Jie Xue
Geometric matching is an important topic in computational geometry and has been extensively studied over decades. In this paper, we study a geometric-matching problem, known as geo…
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +2
In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of points in called terminals and a parameter , and the goal is to compute a Ste…
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 …
Minimum-Membership Geometric Set Cover, Revisited
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set of points and a set $\m…
Coresets for Clustering in Geometric Intersection Graphs
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar
Designing coresets--small-space sketches of the data preserving cost of the solutions within -approximate factor--is an important research direction in the study of cente…
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…
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
Sayan Bandyapadhyay, Anil Maheshwari, Michiel Smid
Given two sets and of points in the plane, of total size , a {many-to-many} matching between and is a set of pairs such that , and for e…
FPT Approximation for Fair Minimum-Load Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +2
In this paper, we consider the Minimum-Load -Clustering/Facility Location (MLkC) problem where we are given a set of points in a metric space that we have to cluster and…
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…