Approximating geometrical graphs via “spanners” and “banyans”
Satish B. Rao, Warren D. Smith · 1998
probability l/2 in a Monte Carlo sense2 in time The main result of t,his paper is an improvement of Arora's method to find (l+e) approximations for geometric NP-hard problems including the Euclidean Traveling Salesman Problem and t.he Euclidean Steiner Minimum Tree problems.For f&d dimension d and E, our algorithms run in O(NlogN) time.(s\/;i) O(d(+.&)d-')N + O(dN log N) and (sd)"(d)N + (sfi)"(d(~~)d-') log N (4 An interesting byproduct of our work is the definition and consbruction of banyans, a generalization of graph spxmers.A (1 + e)-banyan for a set of points A is a set of points A' and line segments S wit,h endpoints in A U A' such that a 1 + e optimal Steiner Minimum Tree for any subset of A is contained in S. We give a construction for banyans such that the total length of the line segments in S is within a constant factor of the size of t,he minimum spanning tree of A when e and d are fked.space, or in a Las Vegas sense3 in time 2(ad)"(d) N + O(dNlogN), or a deterministic algorithm with runt,ime 2(sd)"(d) N + (sd) o(d)Nlog N, in both of the latter cases consumingIn thii abbreviated paper, we only provide proofs of these results in two dimensions.The full paper on WDS's web page (http://wuu.neci.nj.nec.com/homepages/wds,click"NECItechnical reports") extends the techniques to higher dimensions, proves some new facts and clarifies some old facts about spanners, and also gives approsimation algorithms for minimum matching, edge cover, rectilinear Steiner minimum tree, and minimum a-matching.(s~)'(~)N + 2(8d)o'd' log N space.Our (1+1/s)-approsimation algorithms for NP-hard problems run more slowly than competing esact algorithms when so(l) > N or do(') > log N, otherwise they run more quicldy. New Ingredients