An instance of the Median Tour Problem (also referred to as the Traveling Circus Problem) is defined by a set P={v¹, ... ,v} of points in the plane and a partition P¹, ... ,P_k of P. The objective is to minimize the length of the Hamiltonian tour through facilities v^ij in Pj, plus the sum of radial distances from the remaining sites to their closest facility. The points may be thought of as villages. Over a given period, a circus will tour some of the villages, while people from the remaining villages will travel to the circus. For the euclidean version of this problem we give an PTAS, i.e. an 1+2SQRT(2)/m-approximation algorithm whose running time is polinomial in n for every fixed integer m. The PTAS is constructed using Mitchells m-Guillotine Subdivisions.
Given a set P={v¹, ... ,v} of points in the plane and an integer 1≤k≤n, in the Newspaper Delivery Problem one is to design a primary tour through a subset of k points of P and secondary tours linking the remaining sites to the primary tour. The total length of all tours is to be minimized. The primary tour may correspond to a newspaper delivery route comprising the printing plant and a number of transfer points. These transfer points are used as anchor points for secondary delivery routes. We describe an 1+1/c-approximarion algorithm for the Euclidean version of this problem which is a PTAS when k=O(n). The construction of the PTAS is dased on an extension of Aroras PTAS for Euclidean TSP.