  In the Steiner Forest problem, we are given terminal pairs $\{s_i, t_i\}$,
and need to find the cheapest subgraph which connects each of the terminal
pairs together. In 1991, Agrawal, Klein, and Ravi, and Goemans and Williamson
gave primal-dual constant-factor approximation algorithms for this problem;
until now, the only constant-factor approximations we know are via linear
programming relaxations.
  We consider the following greedy algorithm: Given terminal pairs in a metric
space, call a terminal "active" if its distance to its partner is non-zero.
Pick the two closest active terminals (say $s_i, t_j$), set the distance
between them to zero, and buy a path connecting them. Recompute the metric, and
repeat. Our main result is that this algorithm is a constant-factor
approximation.
  We also use this algorithm to give new, simpler constructions of cost-sharing
schemes for Steiner forest. In particular, the first "group-strict" cost-shares
for this problem implies a very simple combinatorial sampling-based algorithm
for stochastic Steiner forest.
