5 papers · 1 filter
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…
Sparse Outerstring Graphs Have Logarithmic Treewidth
Shinwoo An, Eunjin Oh, Jie Xue
An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with vertices has…