6 citations · 20 across the 19 of their papers we have counts for
28 papers
Improved Algorithms for Clustering with Noisy Distance Oracles
Pinki Pradhan, Anup Bhattacharya, Ragesh Jaiswal
Bateni et al. has recently introduced the weak-strong distance oracle model to study clustering problems in settings with limited distance information. Given query access to the st…
Fast -means Seeding Under The Manifold Hypothesis
Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal
We study beyond worst case analysis for the -means problem where the goal is to model typical instances of -means arising in practice. Existing theoretical approaches provide…
A New Rejection Sampling Approach to -++ With Improved Trade-Offs
Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal
The -++ seeding algorithm (Arthur & Vassilvitskii, 2007) is widely used in practice for the -means clustering problem where the goal is to cluster a dataset $…
Robust-Sorting and Applications to Ulam-Median
Ragesh Jaiswal, Amit Kumar, Jatin Yadav
Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal…
Quantum (Inspired) -sampling with Applications
Poojan Shah, Ragesh Jaiswal
-sampling is a fundamental component of sampling-based clustering algorithms such as -means++. Given a dataset with points and a center set $C…
FPT Approximation for Capacitated Sum of Radii
Ragesh Jaiswal, Amit Kumar, Jatin Yadav
We consider the capacitated clustering problem in general metric spaces where the goal is to identify clusters and minimize the sum of the radii of the clusters (we call this t…
A Quantum Approximation Scheme for k-Means
Ragesh Jaiswal
We give a quantum approximation scheme (i.e., -approximation for every ) for the classical -means clustering problem in the QRAM model with a…
Universal Weak Coreset
Ragesh Jaiswal, Amit Kumar
Coresets for -means and -median problems yield a small summary of the data, which preserve the clustering cost with respect to any set of centers. Recently coresets have…
Clustering What Matters in Constrained Settings
Ragesh Jaiswal, Amit Kumar
Constrained clustering problems generalize classical clustering formulations, e.g., -median, -means, by imposing additional constraints on the feasibility of clustering. Ther…
Tight FPT Approximation for Constrained k-Center and k-Supplier
Dishant Goyal, Ragesh Jaiswal
In this work, we study a range of constrained versions of the -supplier and -center problems such as: capacitated, fault-tolerant, fair, etc. These problems fall under a broa…
Tight FPT Approximation for Socially Fair Clustering
Dishant Goyal, Ragesh Jaiswal
In this work, we study the socially fair -median/-means problem. We are given a set of points in a metric space with a distance function . There are…
Hardness of Approximation of Euclidean -Median
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal
The Euclidean -median problem is defined in the following manner: given a set of points in , and an integer , find a set $C \subset \mathbb{…
FPT Approximation for Constrained Metric -Median/Means
Dishant Goyal, Ragesh Jaiswal, Amit Kumar
The Metric -median problem over a metric space is defined as follows: given a set of facility locations and a set $C \subseteq \math…
Multiplicative Rank-1 Approximation using Length-Squared Sampling
Ragesh Jaiswal, Amit Kumar
We show that the span of rows of any matrix sampled according to the length-squared distribution contains a rank-$1…
Streaming PTAS for Binary -Low Rank Approximation
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal +1
We give a 3-pass, polylog-space streaming PTAS for the constrained binary -means problem and a 4-pass, polylog-space streaming PTAS for the binary -low rank approximatio…
Streaming PTAS for Constrained k-Means
Dishant Goyal, Ragesh Jaiswal, Amit Kumar
We generalise the results of Bhattacharya et al. (Journal of Computing Systems, 62(1):93-115, 2018) for the list--means problem defined as -- for a (unknown) partition $X_1, ...…
Approximate Correlation Clustering Using Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal
Ashtiani et al. (NIPS 2016) introduced a semi-supervised framework for clustering (SSAC) where a learner is allowed to make same-cluster queries. More specifically, in their model,…
On the k-Means/Median Cost Function
Anup Bhattacharya, Yoav Freund, Ragesh Jaiswal
In this work, we study the -means cost function. Given a dataset and an integer , the goal of the Euclidean -means problem is to find a set of $…
Approximate Clustering with Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal +1
Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind…
Faster Algorithms for the Constrained k-means Problem
Anup Bhattacharya, Ragesh Jaiswal, Amit Kumar
The classical center based clustering problems such as -means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster ar…
Sampling in Space Restricted Settings
Anup Bhattacharya, Davis Issac, Ragesh Jaiswal +1
Space efficient algorithms play a central role in dealing with large amount of data. In such settings, one would like to analyse the large data using small amount of "working space…
A note on the relation between XOR and Selective XOR Lemmas
Ragesh Jaiswal
Given an unpredictable Boolean function , the standard Yao's XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in [k]…
Improved analysis of D2-sampling based PTAS for k-means and other Clustering problems
Ragesh Jaiswal, Mehul Kumar, Pulkit Yadav
We give an improved analysis of the simple -sampling based PTAS for the -means clustering problem given by Jaiswal, Kumar, and Sen (Algorithmica, 2013). The improvement on…
A tight lower bound instance for k-means++ in constant dimension
Anup Bhattacharya, Ragesh Jaiswal, Nir Ailon
The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial centers when using the k-means heuristic. The algorithm is a simple s…