Given an undirected graph G, finding a spanning tree of G with maximum number of leaves
is NP-complete. We use the simple technique of local optimization to provide the first approximation
algorithms for this problem. Our algorithms run in polynomial time to produce locally
optimal solutions. We prove that locally optimal solutions to this problem are globally nearoptimal.
In particular, we prove that two such algorithms have performance ratios of 5 and 3.
The latter algorithm employs more powerful local-improvement steps than the former and hence
has higher running time. This may indicate an interesting trade-off between the performance
ratios and the running times of the series of algorithms we describe.