The maximum f-depth spanning tree problem

✍ Scribed by Jérôme Monnot

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 113 KB
• Volume: 80
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00160-0

✦ Synopsis

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 first prove that the maximization and the minimization versions are equal-approximable under the differential ratio, that measures how the value of an approximate solution is placed in the interval between the worst and the best solution values of an instance. We show that both problems can be approximately 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 approximation for Max f -depthDSTP r which can be improved to 4/5 for Min 2-depthSTP r [1, 2] and 7/8 for Max 2-depthSTP r [1,2].