b'@techreport{DasKapoorSmid96,'b'\nTITLE = {On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees},\nAUTHOR = {Das, Gautam and Kapoor, Sanjiv and Smid, Michiel},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-1996-1-006},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1996},\nDATE = {1996},\nABSTRACT = {We consider the problems of computing $r$-approximate traveling salesman tours and $r$-approximate minimum spanning trees for a set of $n$ points in $\\IR^d$, where $d \\geq 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