Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.DS2024
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,…