11 papers
Subexponential Parameterized Approximation for Group-Fair Euclidean -Center
Rudranarayan Kar, Diya Roy, Abhishek Sahu
Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different grou…
Fair, Efficient and Connected Allocations on Graphs
Susobhan Bandopadhyay, Anish Datta, Palash Dey +2
We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximi…
Exploiting Graph Structure for Near-Optimal Broadcasting
Rudranarayan Kar, Praneet Kumar Patra, Diya Roy +1
Telephone broadcasting is a classical model for spreading information in a network. Given a connected graph with source vertex , each informed vertex may inform exactly…
A Deterministic Separation Lemma
Abhishek Sahu
The \emph{Separation Lemma} is a simple yet powerful tool, akin to the well-known \emph{Isolation Lemma}, that guarantees the uniqueness of certain set sums. Bandopadhyay et al.\ i…
On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
Susobhan Bandopadhyay, Aritra Banik, Diptapriyo Majumdar +1
Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A.…
Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
Aritra Banik, Sujoy Bhore, Palash Dey +1
The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to in…
Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
Aritra Banik, Mano Prakash Parthasarathi, Venkatesh Raman +2
The Minimum Consistent Subset (MCS) problem arises naturally in the context of supervised clustering and instance selection. In supervised clustering, one aims to infer a meaningfu…
Identifying Codes Kernelization Limitations
Aritra Banik, Praneet Kumar Patra, Adele Anna Rescigno +1
The Identifying Code (IC) problem seeks a vertex subset whose intersection with every vertex's closed neighborhood is unique, enabling fault detection in multiprocessor systems and…
Cost-Effective, Low Latency Vector Search with Azure Cosmos DB
Nitish Upreti, Harsha Vardhan Simhadri, Hari Sudan Sundar +33
Vector indexing enables semantic search over diverse corpora and has become an important interface to databases for both users and AI agents. Efficient vector search requires deep…
Towards Transitive-free Digraphs
Ankit Abhinav, Satyabrata Jana, Abhishek Sahu
In a digraph , an arc in is considered transitive if there is a path from to in . A digraph is transitive-free if it does not contain any transitive…
New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
Aritra Banik, Sayani Das, Anil Maheshwari +6
In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph , consisting of a vertex set of size and an edge set .…