Approximating Prize-Collecting Variants of TSP

As mentioned above, the prize-collecting setting is a standard setting for studying algorithmic problems. Theoretically, this is closely related to the Lagrangian relaxation paradigm, where constraints are allowed to be violated by paying some penalty. It is also natural from a practical perspective, where it is often possible to refuse to cover some entity if it incurs too high a cost, paying them some predefined penalty instead. In this article, we study OTSP and Multi-Path-TSP in this setting, which can also be viewed as generalizations of PCTSP.

In the remainder of this section we provide an overview of our algorithms and techniques for PCOTSP and PC-Multi-Path-TSP. The details of the algorithms and the proofs of correctness are covered in the following sections.

In Section 2, we specify the LP relaxation (OLP) of PCOTSP. Our algorithm first solves the LP, and then it samples a tree $T_i$ for each of the $k$ parts of the LP solution, in the manner of Lemma 2 in [8], and Theorem 4 in [13], which are both based on a result of Bang-Jensen, Frank and Jackson [5] and Post and Swamy [21]³³3Post and Swamy showed that the Bang-Jensen, Frank, Jackson decomposition can be computed in polynomial time. (see Lemma 6). The expected cost of each tree is at most the corresponding part of the LP solution, and its expected coverage is at least that of the corresponding $y$ values. Now a key idea in our algorithm is to even out the penalty ratios paid by the algorithm. This is implemented in two ways.

1. 1.

   Probabilistically picking up some of the vertices left out of the sampled trees (inevitably increasing the connection cost). This is achieved through a pick-up threshold, which determines the vertices which should be picked up (with a suitable probability), based on the LP solution.

2. 2.

   Utilizing the spare penalty ratios of sampled vertices to bring down the cost of parity correction.

The second point is realized through an adaptation of the pruning idea from [8] to probabilistically prune away portions of the resultant structure with low connectivity. This allows us to assign weights to the edges of the tree, which, when combined with a suitable multiple of the LP solution, gives a point in the $Q$-join polytope, where $Q$ is the set of odd degree vertices of the current structure. This allows for cheaper parity correction, because the tree edges with higher assigned weights, which are associated with lower value cuts, are pruned with higher probability, and thus the expected cost incurred by them remains low.

The prominent difference between our problem and the standard PCTSP, which necessitates finding new ideas for pruning, is the sampling probability for vertices. In PCTSP, the sampling probability for each vertex $v$ is equal to $y_v$, hence the expected penalty ratio for $v$ is one, and intuitively, there is lots of spare penalty for $v$ to utilize for pruning. But in PCOTSP, the sampling probability of a vertex $v$ is lower (bounded from below by $1-e^{-y_v}$); hence there is little spare penalty ratio left (and for fewer vertices) to utilize for pruning. We obtain an improved adjustment of the pruning by combining our algorithm with a version of the classical algorithm for OTSP [10], which combines the cycle on terminals with a $\frac{3}{2}$-approximation for TSP on the remaining vertices. If the length of the cycle on terminals is low, this algorithm already gives a good approximation ratio. If the length of the cycle is large, this fact can be utilized to improve the analysis for parity correction, because we can show that there is no need to assign (nonzero) weights to the cycle edges.

We believe that this view of evening out the penalty ratio of vertices vis-a-vis the optimal LP solution is a useful conceptual tool for approaching prize collecting versions of TSP or other combinatorial optimization problems. In the case of PCOTSP, it is partly realized through the idea of probabilistically including in the solution those vertices which currently have a too high penalty ratio (based on the desired approximation factor). Squeezing out the slack penalty ratio (again, based on the target approximation factor), is achieved through pruning. Here, the specific structure of the OTSP, and the partially constructed solution proves useful; we can show that if the current cycle through the terminals is small, combining the cycle on terminals with the best PCTSP approximation for the rest of vertices gives a good factor, while a large cycle improves the cost of pruning.

In the case of Multi-Path-TSP, Böhm, Friggstad, Mömke, and Spoerhase [13] propose two algorithms, and show that a careful combination of them leads to a good approximation. The first one, which doubles all edges except those on $s_i,t_i$ paths (and is good when the sum of $s_i,t_i$ distances is large) can be adapted to our setting by probabilistically picking up vertices with high penalty ratio, as opposed to picking up all remaining vertices in [13]. We replace their second algorithm, which finds a minimum length forest in which each terminal appears in exactly one of the components and then adds direct $s_i,t_i$ edges with an algorithm that uses Lemma 6 to sample a tree from the related PCTSP, and then adds direct $s_i,t_i$ edges.

In the OTSP, a tour can be decomposed into $k$ paths, between $o_i$ and $o_{i+1}$.⁴⁴4For notational convenience, we identify $o_{k+1}$ with $o_1$. We can take the polyhedron determined by the following inequalities as the relaxation of one such path between two vertices $s$ and $t$.⁵⁵5 Similar to the LP of [4]; see also [12, 8]. For each vertex $v$, the variable $y_v$ indicates its fractional degree in the stroll.

Now, the PCOTSP can be modeled as the following linear program. For $i=1,\mathrm{\dots }k$ we define $x_i$ and $y_i$ to be the vectors ${(x_{i,e})}_{e\in E}$ and ${(y_{i,v})}_{v\in V}$, respectively. For each $i$, the vector $(x_i,y_i)$ is constrained to be a feasible point in the $o_i$-$o_{i+1}$-stroll relaxation, the sum $y_v={\sum }_{i=1}^k{y}_{i,v}$ over all fractional degrees of a vertex $v$ is an indicator of to what degree $v$ is used in the solution. When $v$ is not fully used, i.e., when , the LP has to pay a fractional penalty of ${\pi }_v(1-y_v)$. We will usually refer to the pair $(o_i,o_{i+1})$ as $(s_i,t_i)$, to emphasize that $(x_i,y_i)$ is a fractional tour/stroll from $o_i$ to $o_{i+1}$.

Note that every feasible solution to (OLP) has $y_o=1$ for all terminals $o$. Similar to $y_v$, we will use $x_e$ as a shorthand for ${\sum }_{i=1}^k{x}_{i,e}$. It follows immediately from the LP constraints that $x(\delta (S))\ge 2y_v$ for any $v\in S\subseteq V\setminus O$. By contracting all terminals $o\in O$ into a single vertex $r$, we therefore obtain the relaxation of the normal PCTSP from [8], which also involves a root, which (without loss of generality; see, e.g., [3]) is required to be in the tour. Given a solution $(x,y)$ to (OLP) and some threshold $\rho \in [0,1]$, we define $V_{\rho }≔\{v\in V\mid y_v\ge \rho \}$.

We consider the following simple algorithm for PCOTSP, inspired by [10]. First, directly connect the terminals $o_1,\mathrm{\dots },o_k$ in order, creating a simple cycle $\widehat{C}$. Then, compute a solution to the PCTSP on the same instance. Since all terminals have infinite penalty, every tour $T$ obtained in this way includes all terminals. We obtain an ordered tour of cost $c(T)+c(\widehat{C})$ by following the original cycle $\widehat{C}$ and grafting in the tour at an arbitrary terminal $o\in O$.

Using an $\widehat{\alpha }$-approximation algorithm to solve the PCTSP, we know that the sum of tour- and penalty costs for this solution is at most $\widehat{\alpha }\cdot {\text{opt}}_{\text{PCTSP}}\le \widehat{\alpha }\cdot {\text{opt}}_{\text{PCOTSP}}$. Since $c(\widehat{C})\le {\text{opt}}_{\text{PCOTSP}}$, this immediately implies a $(1+\widehat{\alpha })$-approximation algorithm for PCOTSP. One can see that this algorithm performs even better if we can guarantee that $\widehat{C}$ is small. To be precise, for any $\alpha \ge \widehat{\alpha }$ we obtain an $\alpha$-approximation provided that $c(\widehat{C})\le (\alpha -\widehat{\alpha }){\text{opt}}_{\text{PCOTSP}}$. We therefore may assume $c(\widehat{C})\ge (\alpha -\widehat{\alpha }){\text{opt}}_{\text{PCOTSP}}$ in the analysis of our main algorithm. The currently best value for $\widehat{\alpha }$ is the approximation guarantee of (roughly) 1.599 obtained by [8].

Fix $\alpha =2.097$. We first solve (OLP)⁶⁶6The separation oracle for the LP boils down to separating subtour elimination constraints. Hence the LP can be solved in polynomial time using the ellipsoid algorithm., to get an optimal solution $(x^{\ast },y^{\ast })$. Using the following Lemma 5, we then split off the vertices $v$ for which $y_v\le \theta$, for a parameter $\theta$ to be determined later, to get a solution $(\widehat{x},\widehat{y})$ for the LP were the remaining vertices have a certain minimum connectivity to the terminals. Vertices that have been split off will not be used in our final tour. Instead, we pay the full penalty for them. We state the following lemma for PCOTSP, as the proof is identical to the one for PCTSP.

Lemma 5 ensures that we can remove vertices from the support of $x$, without increasing the cost of $x$. Since we only split off vertices for which $y_v^{\ast }$ is relatively low, we can afford to pay the additional penalties if we set $\theta =1-\frac{1}{\alpha }$ (we will prove this in Section 3.1). We proceed by sampling a set of trees based on $(\widehat{x},\widehat{y})$.

Lemma 6 can be used to sample a random tree of expected cost at most $c(x)$ which contains each vertex $v$ with probability at least $y_v$ and is guaranteed to connect $s$ to $t$. It is straightforward to see that this can be achieved by choosing each tree $T\in 𝒯$ with probability $\mu (T)$.

For each component $({\widehat{x}}_i,{\widehat{y}}_i)$ of our solution, we apply Lemma 6 and sample a tree $T_i$ as we have described. Define $T:={\dot{\bigcup }}_{i=1}^k{T}_i$. Note that $T$ is no longer a tree, and it might even have repeated edges.

In this subsection, we prove the following lemma:

We note that we can express the expected total penalty cost paid by our algorithm as ${\sum }_{v\in V}{\pi }_v\cdot \text{Pr}\left[v\notin V(T^{\prime \prime })\right]$. We can thus prove Lemma 9 by showing that for each vertex $v$, the ratio $\text{Pr}\left[v\notin V(T^{\prime \prime })\right]/(1-y_v^{\ast })$ is at most $\alpha$.

Due to Step 2 in Algorithm 1, i.e., due to the splitting-off step, $T^{\prime \prime }$ spans only vertices whose $y$-value is at least $\theta$. Vertices $v$ with are therefore included in $V(T^{\prime \prime })$ with probability 0. However, our choice of $\theta =1-\frac{1}{\alpha }$ guarantees that for the vertices $v$ with , we have $\text{Pr}\left[v\notin V(T^{\prime \prime })\right]/(1-y_v^{\ast })\le 1/(1-\theta )=\alpha$. To continue our analysis for the remaining vertices, i.e., those with $y_v^{\ast }\ge \theta$, we show the following lemma:

In order to analyze the expected cost of both the parity correction step and of our final tour, we first need to further investigate the structure of our computed solution and introduce some additional notation. Recall that $T$ denotes the union of all sampled trees and that it includes the closed walk $C$, which is obtained by joining all $s_i$-$t_i$-paths $P_i\subseteq T_i$. Let $R$ be the graph that contains all remaining edges, i.e., the (multi-)graph induced by $E(T)\setminus E(C)$.

While it is convenient to think of $C$ as a cycle, note that the paths $P_1,\mathrm{\dots },P_k$ are not necessarily vertex disjoint. However, we can guarantee that $C$ is a Eulerian multigraph spanning all terminals. In the same sense, $R$ can be thought of as a collection of small trees which are all rooted at the cycle $C$ (in reality, some of those trees may intersect each other). In the following, we will call the edges of $C$ cycle edges and the edges of $R$ tree edges. A depiction of $C$ and $R$ can be seen in Fig. 1.

When we prune the trees $T_i$ into $T_i^{\prime }$, the paths $P_i$ are not affected (because the pruning step guarantees that $o_i$ and $o_{i+1}$ stay connected in $T_i^{\prime }$). So our pruning step can only remove edges from $R$. We thus define $\text{core}(R,\gamma )$ as the graph that is obtained by pruning all trees in $T$ with pruning threshold $\gamma$ and then removing the cycle $C$. We now partition the edge set of $R$ into layers. Intuitively, the $i$-th layer of $R$ contains those edges that are contained in $\text{core}(R,\gamma )$ if and only if $\gamma$ does not exceed some value ${\eta }_i$.

Let ${\eta }_1>\mathrm{\dots }>{\eta }_{\mathrm{\ell }}$ be the $y^{\ast }$-values of all vertices that might be affected by our pruning step, i.e., $\{{\eta }_1,\mathrm{\dots },{\eta }_{\mathrm{\ell }}\}=\{y_v\mid v\in V\text{ and }\theta \le y_v\le {\sigma }_0\}\cup \{{\sigma }_0\}$. By definition, we always have ${\eta }_1={\sigma }_0$. Now let $E_1=\text{core}(T,{\eta }_1)$ and $E_i=\text{core}(T,{\eta }_i)\setminus E_{i-1}$ for $i=2,\mathrm{\dots },\mathrm{\ell }$. One can see that $E_1\cup E_2\cup \mathrm{\dots }\cup E_{\mathrm{\ell }}$ is a partitioning of $E(R)$.

To be able to bound the cost of the cheapest $\text{odd}(T^{\prime \prime })$-join $J$ , we define the following vector

where $\beta =\frac{1}{3{\sigma }_0-\theta }$. To simplify future arguments, we also define the two components $z_{\gamma }$ and $z_{\sigma }$ of $z$, as specified in (1). We remark that the vector $\beta x+z_{\gamma }$ has been used (for a different value of $\beta$) in [8]. In Section 3.3, the cost of $z$ will be used as an upper bound for $c(J)$. To this end, we now prove the following lemma.

In this section, we show the following bound on the cost of our computed tour:

The total cost of our computed tour can be bounded from above by

Our bound on the cost of $J$ is given by the cost of the parity correction vector $z=\beta x+z_{\gamma }+z_{\sigma }$. We start by analyzing the expected combined value of $c(T^{\prime })$ and $c(z_{\gamma })$.

The main idea of the proof of Lemma 13 is that the weight which each layer $E_i$ is assigned in $z_{\gamma }$ is large when ${\eta }_i$ is small and vice versa. At the same time, the chance for layer $E_i$ to be present after pruning and thus to contribute at all to both $z_{\gamma }$ and $c(T^{\prime })$ is an increasing function of ${\eta }_i$. By balancing out these two values, we obtain an upper bound or the contribution of all layers in $R$ to $c(T^{\prime })+c(z_{\gamma })$. At the same time we take into account that the cycle $C$ only contributes toward $c(T^{\prime })$ but crucially not towards the cost of the parity correction vector. This is where we utilize our assumption that $\widehat{C}$ and therefore also $C$ can be lower bounded by a constant fraction of opt. For formally proving Lemma 13, we need the following technical Lemma 14.