PaperlayerView exact revision on arXiv

Source-linked AI summary

The Tight Competitive Ratio of Greedy for Online Steiner Forest

Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade

arXiv:2610.40569v1cs.DS

TL;DR

The competitive ratio of greedy remained difficult to determine despite an O(log^2 k) bound and an O(log k)-competitive conjecture. The upper-bound analysis tracks greedy components through lifetime trees and replaces dense regions of an evolving reference forest, while the lower bound uses harmonically priced shortcut edges. Θ(log k log log k) is the worst-case competitive ratio of greedy for online Steiner Forest.

  • Problem

    The competitive ratio of greedy remained difficult to determine despite an O(log^2 k) bound and an O(log k)-competitive conjecture.

    Source: §1 · p. 2

  • Method

    The upper-bound analysis tracks greedy components through lifetime trees and replaces dense regions of an evolving reference forest, while the lower bound uses harmonically priced shortcut edges.

    Source: §2.1 · p. 6, §2.2 · p. 12

  • Results

    Θ(log k log log k) is the worst-case competitive ratio of greedy for online Steiner Forest.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The matching bounds refute the O(log k) conjecture and show that the additional log log k factor is necessary.

    Source: §1 · p. 2

    The upper-bound sketch assumes k≥4, though formal shifted-logarithm bounds also cover smaller inputs.

    Source: §2.1 · p. 5

Abstract

from arXiv · show

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(log^2 k)$-competitive and conjectured an $O(log k)$ bound, where $k$ 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 $\Theta(log(k) log log(k))$. Specifically, we establish an $O(log(k) log log(k))$ upper bound for arbitrary instances and construct a matching $\Omega(log(k) log log(k))$ lower bound. Our results refute the $O(log k)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight $\Theta(log log k)$ separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.

1 Introduction

Greedy serves each arriving terminal pair on a shortest path after treating previously purchased edges as free, but its general competitive ratio was unresolved. This paper proves a tight Θ(log k log log k) ratio and places that result in the context of earlier online and offline Steiner Forest work.

1 Introduction

  • Greedy connects each arriving pair along a shortest path after making purchased edges free; Awerbuch, Azar, and Bartal proved an O(log^2 k) bound and conjectured O(log k).The online algorithm must serve pairs in arrival order, and purchased edges cannot be removed.Source: §1 · p. 2

1.2 Related Work

  • Online Steiner Tree has an O(log k)-competitive algorithm [IW91], while Berman and Coulston achieve O(log k) for Steiner Forest by buying extra edges beyond the current cheapest route.Offline greedy and local-search algorithms use different rules from the online fixed-pair greedy algorithm analyzed here [GK15] [GGK+18].Source: §1 · p. 2, §1.2 · p. 4

1 Introduction

  • Earlier O(log k log log k) analysis covered only inputs with polylogarithmically bounded pair contraction, while this paper removes that restriction using lifetime trees and reference-forest replacements.The upper-bound analysis tracks greedy components through lifetime trees and replaces dense regions of an evolving reference forest.Source: §1 · p. 2

1.1 Main Results

  • Θ(log k log log k) is the worst-case competitive ratio of greedy, with a matching O(log k log log k) upper bound and Ω(log k log log k) lower bound.The result refutes the O(log k) conjecture and shows the additional log log k factor is necessary.Source: §1 · p. 2, §1.1 · p. 3

2 Overview of the Proofs

The section overviews proofs of a tight Θ(log k log log k) competitive ratio, establishing the upper bound through evolving-forest charging and the matching lower bound using harmonically priced shortcut edges. For the upper bound, it describes encoding low-test-cost walks as forest-run and shortcut-traversal patterns, then controlling their probabilities with random matching exposure and an exponential-moment sum.

2.1 Upper Bound: Evolving the Optimal Forest Across Scales

  • The upper bound partitions payments into O(log k) doubling cost batches and compares them with a reference forest that can shrink through profitable replacements.Small-tree pairs are charged with O(log log k) overhead, while dense clusters enable replacing costly regions of the evolving forest.Source: §2.1 · pp. 5–6
  • When greedy components merge, the heaviest participating component keeps its label and absorbs lighter components; each retained large pair supplies an auxiliary pair with a realizing path of original cost at most 28L^3ρ.Source: §2.1 · p. 7
  • The proof bounds small-tree payments by O(log log k) times reference-forest cost and uses dense-core forest surgery to reduce that cost while preserving marked connections.The surgery replaces core zones with a subgraph costing at most half their prior cost plus O(mρ log^3 k).Source: §2.1 · pp. 8–9
  • Strided batch classes limit future-mark overhead, and summing their charging bounds across classes and batches gives O(OPT log k log log k).The class stride is Θ(log log k); each class contributes O(OPT log k).Source: §2.1 · p. 10

2 Overview of the Proofs

  • An O(log k log log k) upper bound and matching Ω(log k log log k) lower bound establish the greedy algorithm’s tight Θ(log k log log k) ratio.Source: §2.1 · p. 10, §2.2 · p. 11

2.2 Lower Bound: Harmonically Priced Shortcut Edges with Future Edges Present

  • A lower-bound family places all endpoints on a unit-cost path and presents a ranked matching of shortcut edges at decreasing harmonic prices, forcing greedy to buy costly shortcuts.The path costs at most N−1, while the harmonic price schedule yields ALG/OPT = Ω(log k log log k); a short prefix of ranks is skipped.Source: §2.2 · pp. 10–11
  • For each rank, a test graph prices earlier shortcuts at zero and future shortcuts at their offered costs; a random ordered matching makes a rank bad with probability O(N^-1/2/α).Conditioning on a fixed endpoint’s edge having rank i leaves the matching uniform and the remaining ranks independently uniform over other edges.Source: §2.2 · p. 11
  • A candidate path alternates nonempty monotone runs along F with distinct shortcut traversals, and is encoded by its run lengths and directions.With r shortcut traversals, the path has r+1 forest runs and ℓ forest steps, where r+1 ≤ ℓ ≤ R.Source: §2.2 · p. 11
  • After lazily exposing r matching edges on a completed non-aborted walk, the unexposed matching remains uniform, so M(u) is equally likely to be any remaining unexposed vertex other than u.Thus the conditional probability that M(u) is the walk's endpoint z is 1/(N−2r−1).Source: §2.2 · p. 12
  • Choosing θ=Θ(α) cancels the 1/α distance-budget factor, keeping the Markov factor e^(θR)=e^Θ(L) independent of α and at most N^1/2.The tilt must be large enough to damp walks with many shortcut traversals.Source: §2.2 · p. 12
  • The future-rank damping gives β≤2α, and summing the geometric series over all forest-run patterns yields O(1/α).The single-run sum is at most 1/(4α), so the pattern-series ratio aβ is below 1/2.Source: §2.2 · p. 12

4. Deterministic selection and tie-breaking-independent greedy execution. We define 𝐵= Í

The lower-bound construction selects a matching with substantial retained shortcut price and makes greedy purchase each retained shortcut regardless of tie-breaking. It yields the claimed lower bound, including for every sufficiently large request count.

4. Deterministic selection and tie-breaking-independent greedy execution

  • The construction pays Ω(OPT log k log log k) by presenting retained shortcut pairs in rank order and forcing greedy to buy each shortcut at its full price.An induction shows every alternate path avoiding the shortcut’s subdivision vertex costs more, so greedy’s purchase is unique regardless of tie-breaking.Source: §4 · p. 13
  • An ordered matching exists whose good ranks retain at least S0/2 total price; choosing the first such matching lexicographically makes the construction deterministic.The passage states existence but does not include the preceding expectation calculation.Source: §4 · pp. 12–13
  • The lower-bound family extends to every sufficiently large request count by choosing a consecutive parameter level and padding with repeated served pairs.Consecutive levels change log k and log log k by only constant factors.Source: §4 · p. 13

3 Preliminaries

The preliminaries specify the graph and request-sequence setting, define the residual distances used to describe greedy’s payments, and state the conventions for OPT and logarithms.

3 Preliminaries

  • The setting is a finite undirected graph with strictly positive edge costs and a sequence of connected terminal pairs.For an edge set T, the passage begins defining its cost as c(T).Source: §3 · p. 13
  • Subdivision replaces an edge by a path through new degree-two vertices whose positive edge costs sum to the original cost, preserving distances between original vertices.Subdivision vertices are not terminals.Source: §3 · p. 13
  • Before each request, greedy assigns zero residual cost to previously purchased edges and original cost to all others; its payment equals the residual shortest-path distance.The passage also defines residual distances after all pairs have been connected.Source: §3 · p. 13
  • OPT is the minimum cost of a forest connecting all pairs, and the discussion restricts to OPT > 0 because greedy also pays zero when OPT = 0.Unqualified logarithms are natural; terminal pairs with zero payment contribute nothing.Source: §3 · p. 13

4 The Upper Bound

The upper-bound proof develops an evolving reference-forest strategy to control pair payments through cost savings, cycle-rank bounds, and decompositions of reference trees into zones and dense-core replacements. It also separates batches into strided classes to limit mark-reconnection overhead while preserving marked-vertex connections without increasing reference-forest cost.

4.1 Architecture of the Analysis and Cost Batches

  • The analysis updates a reference forest from the optimum, replacing expensive regions with greedy-purchased paths when dense connections permit and charging the replacements to forest-cost reductions.The forest starts at cost OPT and remains nonnegative, so reductions within each strided class between resets total at most OPT.Source: §4.1 · p. 14

4.2 Approaching Greedy: Component Lifetimes and Auxiliary Pairs

  • For large-batch pairs, the analysis extracts auxiliary pairs separated by residual distance at least ρ/2 and joined by original-cost paths of at most 28L^3ρ, setting aside corner cases totaling at most ALG/32.The auxiliary endpoints lie in large reference trees; the paths enable later charging to the evolving forest.Source: §4.2 · pp. 15, 17
  • Maximum-cost component labels ensure the total cost of all greedy-component lifetime trees is at most L·ALG.When components merge, the merged component inherits the label of a touched component with maximum original cost, and retired labels’ components at least double in cost.Source: §4.2 · pp. 16, 18

4.3 Cycle Rank and Small-Tree Charging

  • If every cycle in a multigraph has length at least τ, its cycle rank r satisfies rτ ≤ 4L(r)S, where S is its total edge length.The analysis applies this cycle-rank bound to limit the number of terminal pairs with payment at least τ that the reference forest can connect.Source: §4.3 · pp. 20–21
  • For a cost batch of scale ρ, the small pairs’ total payment is at most 288L(L)c(F†), where L(L)=Θ(log L).The bound applies to pairs whose endpoints lie in reference trees costing less than 216L^3ρ.Source: §4.3 · pp. 21–22

4.4 Approaching OPT: Zone Decomposition, Dense Core, and Forest Surgery

  • Each large reference tree can be partitioned into edge-disjoint zones costing between 2^16 L^3ρ and 3·2^16 L^3ρ, with at most c(F†)/(2^16 L^3ρ) zones overall.The decomposition is constructed bottom-up, accumulating connected leftover subtrees into zones.Source: §4.4 · pp. 22–23
  • The zone multigraph has at most μ loops per vertex and μ parallel edges per pair; discarded-edge payments total at most 2^29 L(L)c(F†), and each core zone has at least 2^13−1 distinct neighbors.Here L(L)=Θ(log L).Source: §4.4 · pp. 24–25
  • The forest update preserves every connection among marked vertices and does not increase reference-forest cost; the dense-core analysis relates retained auxiliary edges to cycle rank.The core charging subgraph has cycle rank at least qcore/2, which the proof uses to relate retained-edge payments to forest cost savings.Source: §4.4 · pp. 26, 28
  • Each batch’s payments are bounded by 64LΔ + O(log L)c(F†), plus 225L^4mρ for preserving connectivity among m marked vertices.Source: §4.5 · p. 29

4.5 Strided Batch Classes and Proof of Theorem 1

  • Strided classes with h = Θ(log L) limit future-mark reconnection overhead to c(F†); within each class, F† starts at F* and never increases in cost.The scale gaps between consecutive batches in a class make the number of future marks small enough to achieve this overhead bound.Source: §4.5 · pp. 29–30
  • O(log k log log k) upper bound: Theorem 1 assembles batch payments while bounding total reference-forest savings by OPT within each class.The proof also uses L = Θ(log(2k)) and h, L(L) = Θ(log log(4k)).Source: §4.5 · p. 31

5 The Lower Bound

The lower-bound construction uses a unit-cost path as a cheap offline connector and ranked matching shortcuts as candidate online requests. It retains shortcuts that pass an alternate-route test, yielding a lower-bound instance where greedy pays for each retained shortcut.

5.1 The comparison path and candidate shortcuts

  • The comparison graph is a unit-cost path on N vertices, and a perfect matching supplies K=N/2 candidate shortcuts with distinct ranks.The path connects all candidate endpoints, so its cost N−1 upper-bounds OPT.Source: §5.1 · p. 31

5.2 Prices and the test for a forced purchase

  • For positive ranks, shortcut prices scale inversely with rank after a zero-price prefix that is used only in the analysis.The prefix edges are excluded from the actual instance.Source: §5.2 · p. 32
  • A shortcut is good only if deleting it leaves every alternate route between its endpoints costlier than its price, even when all other candidates remain available.The test makes earlier-ranked shortcuts free, keeps later ones at their prices, and uses unit costs on the path; removing excluded edges cannot shorten alternate routes.Source: §5.2 · p. 32

5.3 Why few shortcuts fail the test

  • Lazy exposure of a random matching bounds the weighted contribution of each possible alternate-path pattern, while exponential path weights help count routes cheap enough to make a shortcut bad.Each pattern consists of matching traversals separated by nonempty monotone path runs; the weights suppress costly routes, and the resulting probability bound is used to control bad ranks.Source: §5.3 · pp. 33–36

5.4 Retaining enough price and choosing a fixed matching

  • A fixed ordered matching exists whose bad positive-price edges lose at most half the total available positive price.The random choice proves existence; a finite lexicographic search specifies one matching satisfying the bound.Source: §5.4 · p. 37

5.5 The actual instance and greedy’s behavior

  • Greedy buys each retained shortcut’s private two-edge path because every alternate route costs more than its price, making that path the unique simple shortest path.Subdivision vertices keep the actual graph simple, and the behavior does not depend on shortest-path tie-breaking.Source: §5.5 · pp. 37–38

5.6 The competitive ratio

  • For every sufficiently large k, padding the constructed instance preserves the same asymptotic lower bound and changes neither greedy’s cost nor the optimum.The path connects every retained pair and costs N−1; the construction’s lower bound is at least N/L.Source: §5.6 · pp. 38–39
Loading 2610.40569v1…