9 papers
A Configuration-LP Framework for Connected -Median Clustering
Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
We study the \emph{connected -median} clustering problem, a clustering problem that augments the classical -median objective with connectivity constraints. We focus on the \e…
A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching
Yi-Jun Chang, Kushagra Chatterjee
We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs using only a few shared random bits. Specifically, in the $\c…
Creating Robust and Fair Graph Structures for Connectivity and Clustering
Kushagra Chatterjee
Graph algorithms are central to large-scale applications such as navigation systems, social networks, and data analysis platforms. This thesis studies two important challenges in s…
A Generic Framework for Fair Consensus Clustering in Streams
Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das +1
Consensus clustering seeks to combine multiple clusterings of the same dataset, potentially derived by considering various non-sensitive attributes by different agents in a multi-a…
Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications
Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das +1
Clustering is a fundamental task in machine learning and data analysis, but it frequently fails to provide fair representation for various marginalized communities defined by multi…
Towards Fair Representation: Clustering and Consensus
Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das +2
Consensus clustering, a fundamental task in machine learning and data analysis, aims to aggregate multiple input clusterings of a dataset, potentially based on different non-sensit…
Online fair division with arbitrary entitlements
Kushagra Chatterjee, Biswadeep Sen, Yuhao Wang
The division of goods in the online realm poses opportunities and challenges. While innovative mechanisms can be developed, uncertainty about the future may hinder effective soluti…
Popular Edges with Critical Nodes
Kushagra Chatterjee, Prajakta Nimbhorkar
In the popular edge problem, the input is a bipartite graph where and denote a set of men and a set of women respectively, and each vertex in h…
Pairwise Reachability Oracles and Preservers under Failures
Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary
In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let be a directed graph on -no…