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, α _opt^tsp √ n + o(√ n ), where 1.075 α _opt^tsp 1.414. The cost of the minimum matching of n points in the unit square is shown to be, in the worst case, α _opt^mat √ n + o(√ n ), where 0.537 α _opt^mat 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.