7 papers · 1 filter
Improved Algorithms and Lower Bounds for Parametrized Metrical Service Systems
Junhao Gan, Xiao Sun, Seeun William Umboh
We consider the parametrized setting of the classical metrical service system (MSS) problem first studied by Bubeck and Rabani (APPROX/RANDOM 2020). In this setting, the adversary…
Online Matching with Size-Based and Convex Delays
Junhao Gan, Xiao Sun, Seeun William Umboh
We study the online min-cost perfect matching with delay (MPMD) problem where requests arrive in a metric space of points. In MPMD, an algorithm can choose to match a reque…
A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
Philip Cervenjak, Junhao Gan, Naonori Kakimura +2
Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies.…
-Round MPC Algorithms for Multi-dimensional Grid Graph Connectivity, EMST and DBSCAN
Junhao Gan, Anthony Wirth, Zhuo Zhang
In this paper, we investigate three fundamental problems in the Massively Parallel Computation (MPC) model: (i) grid graph connectivity, (ii) approximate Euclidean Minimum Spanning…
Optimal bounds on a tree inference algorithm
Jack Gardiner, Lachlan L. H. Andrew, Junhao Gan +2
This paper tightens the best known analysis of Hein's 1989 algorithm to infer the topology of a weighted tree based on the lengths of paths between its leaves. It shows that the nu…
Optimal Dynamic Parameterized Subset Sampling
Junhao Gan, Seeun William Umboh, Hanzhi Wang +2
In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,~, of~ items, where each item,~, has a…