The maximum f-depth spanning tree problem

This paper deals with the problem of constructing directed trees of optimal weight and root r with depth at most f(\V \) (called f-depthDSTP(r)). We f irst prove that the maximization and the minimization versions are equal-ap proximable under the differential ratio, that measures how the value of an approximate solution is placed in the interval between the worst and the be st solution values of an instance. We show that both problems can be approx imately solved, in polynomial time, within differential ratio bounded above by (lim inf f - 1)/lim inf f. Next, we demonstrate that, when dealing with edge distances 1 and 2, undirected graphs and f (n) = 2 (called 2-depthSTP (r)[1,2]), we improve the ratio to 3/4. Based upon these results, we obtain new bounds for standard ratio: a (lim inf f - 1)/lim inf f-standard approx imation for Max f-depthDSTP, which can be improved to 4/5 for Min 2-depthST P(r)[1,2] and 7/8 for Max 2-depthSTP(r) [1,2]. (C) 2001 Elsevier Science B. V. All rights reserved.