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]