Poojan Shah

collaborators

4 papers

cs.DS2026

Noisy k-means++ is Not too Noisy

Poojan Shah

The celebrated $k$ -means++ algorithm of Arthur and Vassilvitskii (SODA 2007) achieves an $O (lo g k)$ expected approximation for the classical $k$ -means problem using $D^{2}$ -sampling…

cs.DS2026

Fast $k$ -means Seeding Under The Manifold Hypothesis

Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal

We study beyond worst case analysis for the $k$ -means problem where the goal is to model typical instances of $k$ -means arising in practice. Existing theoretical approaches provide…

quant-ph2025

Quantum (Inspired) $D^{2}$ -sampling with Applications

Poojan Shah, Ragesh Jaiswal

$D^{2}$ -sampling is a fundamental component of sampling-based clustering algorithms such as $k$ -means++. Given a dataset $V \subset R^{d}$ with $N$ points and a center set $C…

cs.DS2025

A New Rejection Sampling Approach to $k$ - $means$ ++ With Improved Trade-Offs

Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal

The $k$ - $means$ ++ seeding algorithm (Arthur & Vassilvitskii, 2007) is widely used in practice for the $k$ -means clustering problem where the goal is to cluster a dataset $…

Noisy k-means++ is Not too Noisy

Fast k-means Seeding Under The Manifold Hypothesis

Quantum (Inspired) D2-sampling with Applications

A New Rejection Sampling Approach to k-means++ With Improved Trade-Offs

Fast $k$ -means Seeding Under The Manifold Hypothesis

Quantum (Inspired) $D^{2}$ -sampling with Applications

A New Rejection Sampling Approach to $k$ - $means$ ++ With Improved Trade-Offs