A PTAS for TSP with Neighbourhoods over Parallel Line Segments

The Travelling Salesman Problem (TSP) is one of the most fundamental and well-studied problems in combinatorial optimization due to its wide range of applications. In TSP, one is given a set of points in a metric space and the goal is to find a (closed) tour (or walk) of minimum length visiting all the points. For several decades, the classic algorithm by Christofides [10] and independently by Serdyukov [32] which implies a $\frac{3}{2}$-approximation was the best-known approximation for TSP until a recent result in [24] which shows a slight improvement. Several generalizations (or special cases) of TSP have been studied as well, the most notable is when the points are given in fixed dimension Euclidean space. Arora and Mitchell [4, 30] presented different PTASs for (fixed dimension) Euclidean TSP. There have been many papers that have extended these results. Arkin and Hassin [3] introduced the notion of TSP with neighbourhoods (TSPN).

An instance of TSPN is a set of neighbourhoods (or regions) given in a metric space, and the goal is to find a minimum length (or cost) tour that visits all these regions. Each region can be a single point or could be defined by a subset of points. They gave several $O(1)$-approximations for the geometric settings where each region is some well-defined shape on the plane, e.g. disks, and parallel unit length segments. Several papers have studied TSPN for various classes of neighbourhoods and under different metrics.

TSPN is much more difficult than TSP in general and in special cases, just as group Steiner tree is much more difficult than Steiner tree (one can consider each neighbourhood as a group/set from which at least one point needs to be visited). In group Steiner tree or group TSP, one is given a metric along with groups of terminals (each group is a finite set). The goal is to find a minimum cost Steiner tree (or a tour) that contains (or visits) at least one terminal from each group. TSPN generalizes group TSP by allowing infinite size groups. Using the hardness result for group Steiner tree [22], it follows that general TSPN is hard to approximate within a factor better than $\mathrm{\Omega }({\log }^{2-\epsilon }n)$ for any $\epsilon >0$ even on tree metrics. The algorithms for group Steiner tree on trees in [20], and embedding of metrics onto tree metrics in [18], imply an $O({\log }^{3}n)$-approximation for TSPN in general metrics. Unlike Euclidean TSP (which has a PTAS), TSPN is APX-hard on the Euclidean plane (i.e. ${ℝ}^2$) [11]. The special case when each region is an arbitrary finite set of points in the Euclidean plane (group TSP) has no constant approximation [31] and the problem remains APX-hard even when each region consists of exactly two points [13].

Focusing on Euclidean metrics, most of the earlier work have studied the cases where the regions (or objects) are fat. Roughly speaking, it usually means the ratio of the smallest enclosing circle to the largest circle fitting inside the object is bounded. There are some work on when regions are not fat, most notably when the regions are (infinite) lines or line segments or in higher dimensions when they are hyperplanes. For the case of infinite line segments on ${ℝ}^2$, the problem for $n$ lines can be solved exactly in $O(n^4\log n)$ time by a reduction to the Shortest Watchman Route Problem (see [12, 23]). For the same setting, Dumitrescu and Mitchell [14] presented a linear time $\frac{\pi }{2}$-approximation, which was improved to $\sqrt{2}$ by Jonsson [23] (again in linear time). For infinite lines in higher dimensions (i.e. $\ge 3$), the problem is proved to be APX-hard (see [2] and references there). For neighbourhoods being hyperplanes and dimension being $d\ge 3$, Dumitrescu and Tóth [15] present a constant factor approximation (which grows exponentially with $d$). For arbitrary $d$, they present an $O({\log }^{3}n)$-approximation. For any fixed $d\ge 3$, authors of [1] present a PTAS.

For parallel (unit) line segments on the plane (${ℝ}^2$) Arkin and Hassin [3] presented a $(3\sqrt{2}+1)$-approximation which was improved to $3\sqrt{2}$ by [14], which remains the best-known approximation for this case as far as we know for over two decades. Authors of [17] proved that TSPN for unit line segments (in arbitrary orientation) is APX-hard. In this paper, we settle the approximability of TSPN when regions are parallel line segments of similar length (unit length is a special case) and present a PTAS for it. As mentioned above, the best-known approximation for unit length parallel segments has ratio $3\sqrt{2}$ [14]. We first focus on the case of unit line segments and show how our result extends to when line segments have bounded length ratio. This is in contrast with the APX-hardness of [17] for unit line segments with arbitrary orientation. Our result also implies a $(2+\epsilon )$-approximation for the case where the segments can be both vertical and horizontal.

Suppose we are given $n$ vertical line segments $s_1,\mathrm{\dots },s_n$ of lengths in the range $[1,\lambda ]$ for some constant $\lambda \ge 1$, and the top and bottom points of each $s_i$ are denoted by $s_i^t$ and $s_i^b$, respectively. These end-points are also called tips of the segment. For any point $p$, let $x(p)$ and $y(p)$ denote the $x$ and $y$-coordinates of $p$, respectively. Similarly, for any segment or vertical line $s$, let $x(s)$ denote its $x$-coordinate. For two points $p,q$, we use $\Vert pq\Vert$ to denote the Euclidean distance between them. A feasible (TSP) tour is specified by a sequence of points where each of these points is on one of the segments of the instance and each line segment has at least one such point, and the tour visits these points consecutively using straight lines. The line that connects two consecutive points in a tour is called a leg of the tour. In our problem, the goal is to find a TSP tour of minimum total length. As mentioned earlier, we focus on the case where all the line segments have length 1 and then show how the proof easily extends to the setting where they have lengths in $[1,\lambda ]$. Fix an optimum solution, which we refer to by OPT and use opt to refer to its cost. Our goal is to show the existence of a near-optimum (i.e. $(1+\epsilon )$-approximate) structured solution that allows us to find it using dynamic programming.

First, we show at a small loss we can assume all the line segments have different $x$-coordinates. We assume that the minimal bounding box of these line segments has length $L$ and height $H$. For now, assume $H>3$ (case of $H\le 3$ is easier, see Theorem 4). Let $B=\max \{L,H-2\}$. So $\text{opt}\ge 2B$; we can also assume $B\le \frac{n}{\epsilon }$, because otherwise $\text{opt}\ge 2n/\epsilon$ and if we consider an arbitrary point on each line segment (say the lower tip) and use a PTAS for the classic TSP for these points, then it will be a PTAS for our original instance as well (because we pay at most an extra +2 for each line for a total of $2n$ which is $O(\epsilon \cdot \text{opt})$). For a given $ϵ>0$, consider a grid on the plane with side length $\frac{ϵB}{n^2}$. Now move each line segment (parallel to the $y$-axis) so that the lower tip of each $s_i$ is moved to the nearest grid point where there is no other line segment $s_i$ with that $x$-coordinate. By doing this, all the segments will have different $x$-coordinates and each segment would move at most , and in total, all segments would move at most a distance of $ϵB$. So the optimum value of the new instance has cost at most $(1+\epsilon )\cdot \text{opt}$. For simplicity of notations, from now on we assume the original instance has this property and let OPT (and opt) refer to an optimum (and its value) of this modified instance.

One special instance of the problem is when there is a horizontal line that crosses all the input segments. This special case can be detected and solved easily. Otherwise, any optimum solution will visit at least 3 points that are not colinear. In such cases, like in the classic (point) TSP [4], we can assume the optimum does not cross itself, i.e. there are no two legs of the optimum $\mathrm{\ell }$ (between points $p,q$) and ${\mathrm{\ell }}^{\prime }$ (between points $p^{\prime },q^{\prime }$) that intersect, as otherwise removing these two and adding the pair of $p{q}^{\prime },p^{\prime }q$ or $p{p}^{\prime },q{q}^{\prime }$ will be a feasible solution of smaller cost.

Note that if a solution is self-crossing, the operation of uncrossing (which reduces the cost) does not increase the shadow

Suppose the sequence of points of OPT is $p_1,p_2,\mathrm{\dots },p_{\sigma }$ and the straight lines connecting these points (i.e. legs of OPT) are ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2,\mathrm{\dots },{\mathrm{\ell }}_{\sigma }$ where ${\mathrm{\ell }}_i$ connects two points $p_i,p_{i+1}$ (with $p_{\sigma +1}=p_1$), and each $s_i$ has at least one point $p_j$ on it. We consider OPT oriented in this order, i.e. going from $p_i$ to $p_{i+1}$. Since all segments have distinct $x$-coordinates, we can assume No two consecutive points $p_i,p_{i+1}$ are on the same line segment by short-cutting (so no leg ${\mathrm{\ell }}_i$ is vertical) and all points $p_i$ on distinct line segments have distinct $x$-coordinates.

As mentioned before, let the length of the sides of the minimal bounding box of an instance of the problem be $L\times H$. By proving the following special case, we show we can instead focus on the cases that $H$ is large.

From now on we assume that $H>3$. Our main goal is to prove Theorem 2.

Since there are no vertical legs, there is no leg that is both to the left and to the right of a segment of the instance at the same time. Consider any segment $s_i$ and suppose that ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$ are the two legs of OPT with common end-point $p_j$ that is on $s_i$. Let $s_i^t$ and $s_i^b$ denote the top and the bottom tips of $s_i$. We consider 3 possible cases for the location of $p_j$ and the arrangement of ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$. Informally, one possibility is that the two legs ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$ form a straight line that crosses $s_i$ at $p_j$; one possibility is that the two legs are touching $s_i$ at one of its tips (i.e. $p_j=s_i^t$ or $p_j=s_i^b$) such that one is to the left and one is to the right of $s_i$ and they don’t make a straight line, and the third possibility is that the two legs ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$ are on the same side (both left or both right) of $s_i$.

For the case of a reflection point $p_j$ with two legs ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$, if both legs are to the left of the segment it is called a left reflection point and otherwise it is a right reflection point. Also note that if ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$ are on the two sides of $s_i$ and $\mathrm{\angle }{\mathrm{\ell }}_i{p}_j{\mathrm{\ell }}_{i+1}\ne \pi$, then $p_j$ must be a tip, or else we could move $p_j$ slightly up or down and reduce the length of OPT (see Figure 2).

If ${\mathrm{\ell }}_j,{\mathrm{\ell }}_{j+1}$ are two legs incident to a reflection point $p$ on a segment $s$, if the angle between ${\mathrm{\ell }}_j$ and $s$ is the same as the angle between ${\mathrm{\ell }}_{j+1}$ and $s$ (i.e. ${\mathrm{\ell }}_{j+1}$ is like the reflection of a ray ${\mathrm{\ell }}_j$ on mirror $s$) then $p$ is called a pure reflection point.

We say a subpath contains a reflection point $p_j$ if $p_j$ is not the start or end vertex of the subpath (i.e. both legs of incident to $p_j$ belong to that subpath.)

As mentioned in the introduction, we follow the paradigm of Arora [4] for designing a PTAS for classic Euclidean TSP with some modifications. We focus more on defining the modifications that we need to make to that algorithm. First, we describe the main algorithm and how it reduces the problem into a collection of instances with a constant-height bounding box. We show how those instances can be solved using another DP (referred to as the inner DP), and how we can combine the solutions for them using another DP (referred to as the outer DP) to find a near-optimum solution of the original instance. Recall that in Section 2, we assumed the minimal bounding box of the instance has length $L$ and height $H$ and we defined $B=\max \{L,H-2\}$, and also we can assume that $B\le \frac{n}{\epsilon }$. We moved each line segment to be aligned with a grid point with side length $\frac{ϵB}{n^2}$ (at a loss of $(1+\epsilon )$ at approximation). Now, we scale the grid (as well as the line segments of the instance) by a factor of $\rho =\frac{4n^2}{ϵB}$ so that each grid cell has size 4. We obtain an instance where each line segment has length $\rho$, all have even integer coordinates, any two segments are at least 4 units apart, and the bounding box has size $N=O(n^2/\epsilon )$. Let this new instance be $ℐ$. Note that if we define cover-lines as before but with a spacing of $\rho$, all the arguments for the existence of a near-optimum solution with a bounded shadow in any strip (the area between two consecutive cover-lines) still hold. We will present a PTAS for this instance. It can be seen that this implies a PTAS for the original instance of the problem. From now on, we use OPT to refer to an optimum solution of instance $ℐ$, and opt to refer to its cost. Note that since the bounding box has side length $N$, then $\text{opt}\ge 2N$. Similar to Arora’s approach, we do the hierarchical dissectioning of the instance into nested squares using random axis-parallel dissectioning lines, and put portals at these dissecting lines. We continue this dissectioning process until the distances between horizontal (and so vertical) dissecting lines is $h\cdot \rho$ for $h=\lceil 1/\epsilon \rceil$. So at the leaf nodes of our recursive decomposition quad-tree, each square is $(h\cdot \rho )\times (h\cdot \rho )$, and the height of the decomposition is $\log (N/\rho h)=O(\log n)$ since $B\le \frac{n}{\epsilon }$. We choose vertical dissecting lines only at odd $x$-coordinates so no line segment of the instance will be on a vertical dissecting line.

We define our cover-lines $C_{\tau }$ based on these horizontal dissecting lines carefully. Consider the first (horizontal) dissecting line we choose, this will be a cover-line, and then moving in both up and down directions from this line, we draw horizontal lines that are $\rho$ apart. These will be all the cover-lines. Label the cover-lines from the top to bottom by $C_1,C_2,\mathrm{\dots },C_{\sigma }$ in that order. As before, the smallest index $\tau$ such that $C_{\tau }$ crosses a line segment is the cover-line that “covers” that line segment. We partition the cover-lines into $h$ groups based on their indices: Group $G_j$ contains all those cover-lines with index $\tau$ where $j=\tau (modh)$. Let $G_{j\ast }$ be the group of cover-lines that includes the first horizontal dissecting line, and hence all the other horizontal dissecting lines as well. The arguments for the case of unit-length line segments to show there is a near-optimum solution in which the shadow in each strip of height $1$ is $O(1/\epsilon )$ (Theorem 2), also imply the same for the scaled instance $ℐ$. Furthermore, if we consider $h$ consecutive strips, i.e. the area between two consecutive cover-lines in the same group $G_j$, then there is a near-optimum solution that has shadow $O(h/\epsilon )=O(1/{\epsilon }^2)$. Our goal is to show that, at a $(1+\epsilon )$-factor loss, we can simply drop the line segments that are intersecting the horizontal dissecting lines (i.e. all those intersecting cover-lines in $G_{j^{\ast }}$) with appropriate consideration of portals (to be described). Removing the line segments that cross the dissecting lines allows us to decompose the instance into “independent” sub-instances that interact only via portals. The details of how to remove these segments which leads to proof of Lemma 25 below are deferred to the full version [21].

Similar to Arora’s scheme for TSP, for $m=O(\frac{1}{\epsilon }\log (N/\rho h))$, we place portals at all 4 corners of a square in the decomposition, plus an additional $m-1$ equally distanced portals along each side (so a total of $4m$ portals on the perimeter of a square of the dissection). For simplicity, we assume $m$ is a power of 2 and at least $\frac{4}{\epsilon }\log (N/\rho h)$. We say a tour is portal respecting if it crosses between two squares in our decomposition only via portals of the squares. A tour is $r$-light if it crosses the portals on each side of a square of the dissection at most $r$ times. For classic (point) TSP, it can be shown that there is a near-optimum solution that is portal respecting and $r$-light for $r=O(1/\epsilon )$. Our goal is to show a similar statement, except that we want the restriction of the tour to each “base” square of side length $O(h\cdot \rho )$ to have bounded (by $O(h/\epsilon )=O(1/{\epsilon }^2)$) shadow as well. We then show that we can find an optimum solution with a bounded shadow for the base cases using a DP. This will be our inner DP. We then show how the solutions of for the 4 sub-squares of a square in our decomposition can be combined into a solution for the bigger subproblem using the outer DP. We show that at a small loss in approximation (i.e. $O(\epsilon \cdot \text{opt})$), we can drop all the line segments of input that are intersecting the horizontal dissecting lines (i.e. covered by a cover-line in group $G_{j^{\ast }}$), solve appropriate subproblems, and then extend the solutions to cover those dropped segments. This modification requires certain portals of each square in the decomposition to be visited in the solution for that square. We show there is a feasible solution that visits all the remaining segments as well as the “required” portals, of total cost at most $(1+\epsilon )\cdot \text{opt}$, and that such a solution can be extended to a feasible solution visiting all the segments of the original instance (i.e. including the ones that we dropped) at an extra cost of $O(\epsilon \cdot \text{opt})$.

The outer DP based on the quad-tree dissection is similar to the classic PTAS for Euclidean TSP. One can show that for $r=O(1/\epsilon )$, there is a $r$-light portal respecting tour for ${ℐ}^{\prime }$ with cost at most $(1+\epsilon )\cdot {\text{opt}}^{\prime }$ where ${\text{opt}}^{\prime }$ is the cost of an optimum solution fo ${ℐ}^{\prime }$. The DP will also “guess” in the recursion for each square, which portals are the “required” portals around it. The base case of this DP will be instances with bounding box of size $\rho \cdot h$. For such instances, we solve the problem using an inner DP. Informally, the inner DP is a nontrivial generalization of the DP for the classic (and textbook example) bitonic TSP in which the shadow is 2. In our case, the shadow is $O(1/{\epsilon }^2)$. We defer the details of both the inner and outer DP to the full version [21].