online learning approach to learning-augmented k-median

We prove clean optimality results for clustering in ultrametrics, identify ways to take advantage of this theory and thoroughly evaluate the resulting techniques.