Combinatorial Optimization (X_401067)

The Euclidean TSP problem on a set P of points in the plane is to compute a shortest tour visiting all the points in P, that is, a tour whose (Euclidean) length is minimized. Suppose we have an algorithm IntegerTSP(P) that, given a set P of n points in the plane with integer coordinates in the range 0, 1, . . . , m, computes a shortest tour in O(nm) time. However, in general, coordinates need not be integral and we do not have a pre-specified range in which the coordinates lie. We will assume though that min p∈P px = min p∈P py = 0, where px and py denote the x- and y-coordinate of the point p. Consider the following PTAS for the general Euclidean TSP problem which simply rounds the coordinates to integers and then applies the IntegerTSP algorithm. PTAS-TSP(P, ϵ) 1. ∆ ← . . . . . . 2. For each point p ∈ P define p ′ = (p ′ x , p′ y ) where p ′ x = ⌈px/∆⌉ and p ′ y = ⌈py/∆⌉. Let P ′ = {p ′ | p ∈ P}. 3. Compute a shortest tour on P ′ using the algorithm IntegerTSP, and return the reported tour (with each point p ′ replaced with its corresponding point p ∈ P. Find a suitable value of ∆ and prove that for your choice of ∆: length(T) ≤ (1 + ϵ)Opt, where T is the tour returned by the algorithm, length(T) is its length, and Opt is the length of an optimal tour on P.