6 papers · 1 filter
Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
Sujoy Bhore, Arnold Filter, Eunjin Oh +2
In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model. A -hash with diameter bound …
Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties
Eunjin Oh, Seongbin Park, Chanho Song
In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets in a metric spac…
Fully Scalable MPC Algorithms for WSPD in Doubling and Euclidean Spaces
Eunjin Oh, Hyeonjun Shin
In this paper, we study the problem of constructing a -well-separated pair decomposition (WSPD) for a point set of size in the Massively Parallel Computation (…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
Seongbin Park, Eunjin Oh
In this paper, we study the many-to-many matching problem on planar point sets with integer coordinates: Given two disjoint sets with , the goal is t…
DAG Covers for Structured Graphs: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,v…