The Maximum -Depth Spanning Tree Problem
Jérôme Monnot · SSRN Electronic Journal · 2001
This paper deals with the problem of constructing directed trees of optimal weight and root with depth at most (||) (called – ). We first prove that the maximization and the minimization versions are equal-approximable under the that measures how the value of an approximate solution is placed in the interval between the worst and the best solutions values of an instance. We show that both problems can be approximately solved, in polynomial time, within differential ratio bounded above by (lim inf − 1)/lim inf . Next, we demonstrate that, when dealing with edge distances 1 and 2, undirected graphs and () = 2 (called 2 − [l,2]), we improve the ratio to 3/4. Based upon these results, we obtain new bounds for : a (lim inf − 1)/ lim inf -standard approximation for − which can be improved to 4/5 for 2 − [l,2] and 7/8 for 2 − [l,2].