P. Agarwal

activity

19992021

most citedEfficient Algorithms for k-Regret Minimizing Sets

22 citations · 43 across the 11 of their papers we have counts for

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2021

Dynamic Enumeration of Similarity Joins

Pankaj K. Agarwal, Xiao Hu, Stavros Sintos +1

This paper considers enumerating answers to similarity-join queries under dynamic updates: Given two sets of $n$ points $A, B$ in $R^{d}$ , a metric $ϕ (\cdot)$ , and a distance…

cs.DS2020

Clustering under Perturbation Stability in Near-Linear Time

Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala +2

We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is $α$ -stable if the underlying opti…

cs.DS2019

Efficient Algorithms for Geometric Partial Matching

Pankaj K. Agarwal, Hsien-Chih Chang, Allen Xiao

Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$ respectively (assume $r \leq n$ ), and let $k$ be a parameter. A matching between $A$ and $B$ is a family of pair…

cs.DS2019★ 3 cited

Faster Algorithms for the Geometric Transportation Problem

Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi +2

Let $R$ and $B$ be two point sets in $R^{d}$ , with $∣ R ∣ + ∣ B ∣ = n$ and where $d$ is a constant. Next, let $λ : R \cup B \to N$ such that $\sum_{r \in R } λ(r) = \sum_…

cs.DS2017★ 22 cited

Efficient Algorithms for k-Regret Minimizing Sets

Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos +1

A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on…