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)
No takes yet. Share an insight, caveat, or question.
Rao et al. (1998) studied this question.