The Travelling Salesman Problem and Minimum Matching in the Unit Square

We show that the cost (length) of the shortest traveling salesman tour through n points in the unit square is, in the worst case, $\alpha _{{\text{opt}}}^{{\text{tsp}}} \sqrt n + o(\sqrt n )$, where $1.075 \leqq \alpha _{{\text{opt}}}^{{\text{tsp}}}\leqq 1.414$. The cost of the minimum matching of n points in the unit square is shown to be, in the worst case, $\alpha _{{\text{opt}}}^{{\text{mat}}} \sqrt n + o(\sqrt n )$, where $0.537 \leqq \alpha _{{\text{opt}}}^{{\text{mat}}} \leqq 0.707$. Furthermore, for each of these two problems there is an almost linear time heuristic algorithm whose Worst case cost is, neglecting lower order terms, as low as b Bible.