betaFeedback

WorksComputer Science

The Tight Competitive Ratio of Greedy for Online Steiner Forest

Abstract

The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges connecting each pair. The natural greedy algorithm connects each terminal pair by a shortest path after making all previously purchased edges free. Awerbuch, Azar, and Bartal (SODA 1996) proved that this algorithm is O(log2k)O(log^2 k)-competitive and conjectured an O(logk)O(log k) bound, where kk is the number of terminal pairs. Bamas, Drygala, and Maggiori (SODA 2022) obtained an O(\log \NumPairs\log\log \NumPairs) bound for greedy on a restricted class of inputs, leaving the general case open. In this paper, we resolve the competitive ratio of the greedy algorithm for online Steiner Forest, proving that it is tightly Θ(log(k)loglog(k))Θ(log(k) log log(k)). Specifically, we establish an O(log(k)loglog(k))O(log(k) log log(k)) upper bound for arbitrary instances and construct a matching Ω(log(k)loglog(k))Ω(log(k) log log(k)) lower bound. Our results refute the O(logk)O(log k) conjecture of Awerbuch, Azar, and Bartal and establish a tight Θ(loglogk)Θ(log log k) separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.

Paper details

vlnc:W_29bbt98y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI’s GPT Astra, Gemini Argon

View statement
Looking for related papers…