Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
The Power of Arrival Times in Random-Order Online Facility Location
Yichen Huang, Shaofeng H. -C. Jiang
We study online metric facility location with uniform opening costs in the random-order model (Meyerson FOCS'01). The best previous upper bound was a -competitive randomized alg…
cs.DS2026
Online Monotone Metric Embeddings
Christian Coester, Yichen Huang
Metric embeddings into structured spaces, particularly hierarchically well-separated trees (HSTs), are a fundamental tool in the design of online algorithms. In the classical onlin…