Universally Optimal Decremental Tree Minima
arXiv:2602.15977v1 Announce Type: new Abstract: An algorithm on weighted graphs is called universally optimal if it is optimal for every input graph, in the worst case taken over all weight assignments. Informally, this means the algorithm is competitive even with algorithms that are optimized for only one specific input graph. Universal optimality was recently introduced [Haeupler et al. 2024] as an alternative to the stronger, but often unachievable instance optimality. In this paper, we extend the concept of […]