1 citations · 2 across the 20 of their papers we have counts for
6 papers · 1 filter
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…
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
Yair Bartal, Ora N. Fandina, Seeun William Umboh
Probabilistic metric embedding into trees is a powerful technique for designing online algorithms. The standard approach is to embed the entire underlying metric into a tree metric…
Online Computation of String Net Frequency
Peaker Guo, Seeun William Umboh, Anthony Wirth +1
The net frequency (NF) of a string, of length , in a text, of length , is the number of occurrences of the string in the text with unique left and right extensions. Recently,…
Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
Tomer Ezra, Stefano Leonardi, Michał Pawłowski +2
The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of…
Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
Philip Cervenjak, Junhao Gan, Seeun William Umboh +1
We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of elements, a collection of subsets of this universe,…