Allen Xiao

activity

20182022

most citedFaster Algorithms for the Geometric Transportation Problem

3 citations · 3 across the 2 of their papers we have counts for

collaborators

5 papers

cs.DS2022

Deterministic, Near-Linear $ε$ -Approximation Algorithm for Geometric Bipartite Matching

Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra +1

Given point sets $A$ and $B$ in $R^{d}$ where $A$ and $B$ have equal size $n$ for some constant dimension $d$ and a parameter $ε > 0$ , we present the first determini…

cs.CG2020

Dynamic geometric set cover and hitting set

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri +2

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) op…

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.CG2018

Approximate Minimum-Weight Matching with Outliers under Translation

Pankaj K. Agarwal, Haim Kaplan, Geva Kipper +4

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a tran…