On the Complexity of Approximating Euclidean Traveling Salesman Tours and Minimum Spanning Trees

We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in \({\Bbb R}^d\) , where d≥ 1 is a constant. In the algebraic computation tree model, the complexities of both these problems are shown to be \(\Theta(n\log(n/r))\) , for all n and r such that r < n and r is larger than some constant. In the more powerful model of computation that additionally uses the floor function and random access, both problems can be solved in O(n) time if \(r=\Theta(n^{1-1/d})\) .

Authors and Affiliations

1. Mathematical Sciences Department, The University of Memphis, Memphis, TN 38152, USA. dasg@next1.msci.memphis.edu. , , , , , , US

   G. Das

2. Department of Computer Science, Indian Institute of Technology, Hauz Khas, New Delhi 110016, India. skapoor@cse.iitd.ernet.in., , , , , , IN

   S. Kapoor

3. Department of Computer Science, King's College London, Strand, London WC2R 2LS, England. michiel@dcs.kcl.ac.uk., , , , , , UK

   M. Smid

Received January 8, 1996; revised July 15, 1996.

Reprints and permissions