  In the online Steiner tree problem, a sequence of points is revealed
one-by-one: when a point arrives, we only have time to add a single edge
connecting this point to the previous ones, and we want to minimize the total
length of edges added. For two decades, we know that the greedy algorithm
maintains a tree whose cost is O(log n) times the Steiner tree cost, and this
is best possible. But suppose, in addition to the new edge we add, we can
change a single edge from the previous set of edges: can we do much better? Can
we maintain a tree that is constant-competitive?
  We answer this question in the affirmative. We give a primal-dual algorithm,
and a novel dual-based analysis, that makes only a single swap per step (in
addition to adding the edge connecting the new point to the previous ones), and
such that the tree's cost is only a constant times the optimal cost.
  Previous results for this problem gave an algorithm that performed an
amortized constant number of swaps: for each n, the number of swaps in the
first n steps was O(n). We also give a simpler tight analysis for this
amortized case.
