2024/10/24 by Borst, Sander, Marek Eliáš, Eliáš, Marek +2 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2410.18542
openalex publication_date 2024/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We propose a O(log k log n)-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of O(log2 k log n) by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic O(log |C| log |F|)-competitive algorithm for non-metric facility location.