Although the problem of finding a minimum spanning tree in a graph can
be solved very efficiently, finding a tree of low cost under two cost
functions simultaneously, say weight and length, is more difficult.
We consider the NP-hard problem of finding a spanning tree that
satisfies a budget L on its length and has the minimum weight among
all spanning trees of length at most L. We present an algorithm that
finds a spanning tree that exactly achieves the minimum weight and
approximates the budget on the length as closely as desired.
[These are results from a paper by R. Ravi and M. X. Goemans, 5th SWAT, 1996]