## 3 Computational Problems and Algorithms
### Maximum Prize Problems
[PERSON] and [PERSON] [28] proposed an integer linear programming approach for optw on a line with unit time windows, which produces approximate solutions within a factor of 4 to the optimal solution. [PERSON] and [PERSON] [23] studied optw with unit time windows. For this variant, they provided \(6+\varepsilon\) and 3 approximation algorithms on graphs and trees respectively. In the case when all time windows have length in [1; 2], [PERSON] and [PERSON] [23] showed that optw admits a 10-approximation algorithm. Finally, [PERSON] et al. [29] studied a different variant of optw where instead of having a time window for each node \(v\), each node \(v\) specifies a subset \(T_{v}\) of available time slots when the tour can visit it and the goal is to find a tour starting from \(s\) that maximizes the number of visited nodes. They call this problem _OrientMTW_ and show that, unless class NP is contained in class \(DTIME(n^{O(\log n)})\), there is no polynomial-time \(o(\frac{\log\log n}{\log\log n})\)-approximation algorithm for OrientMTW even if we restrict the graph topology to trees. **Deadline Traveling Salesman Problem (d-tsp). ** A well-known variant of optw is the Deadline Traveling Salesman Problem (d-tsp). In this case, the release time of each node is assumed to be zero, i.e., \(R(v)=0\) for any vertex \(v\) (formally defined in Figure 5). Since d-tsp is a special case of optw, all results for optw hold for d-tsp. Moreover, [PERSON] et al. [18] gave an \(\mathcal{O}(\log n)\) approximation algorithm for d-tsp while [PERSON] and [PERSON] [30] proposed a \(((1+\varepsilon).\alpha)\)-approximation algorithm for every \(\varepsilon>0\) for d-tsp while exceeding  
Figure 4: Formalization of optw. the deadlines by a factor of \(1+\varepsilon\), where \(\alpha\) is the approximation ratio for d-tsp with a constant number of deadlines (currently \(\alpha=3\) by [PERSON] and [PERSON] [26]). Observe that, on weighted trees, d-tsp admits \((1+\varepsilon)\)-approximation algorithm while violating the deadlines by a factor of \(1+\varepsilon\)[30]. Finally, [PERSON] and [PERSON] [31] proposed a \((7.63+\varepsilon)\)-approximation algorithm for d-tsp in \(n^{O(\log n\Delta)}\) time, where \(n\) is the number of points (nodes), and \(\Delta\) is the diameter of the (scaled) metric space. **Capacitated Orienteering Problem (c-op). ** The c-op is a generalization of op in which we also consider node demands \(r:V\to\mathbb{N}\) and a capacity bound \(C\). Formally, the problem is specified as in Figure 6 Perhaps the most remarkable achievement with respect to this problem is the result of [PERSON] et al. [32] who showed that, given an \(\alpha\)-approximation algorithm for op, it is possible to derive a \(2\alpha\)-approximation algorithm for c-op. [PERSON] and [PERSON] [33] improved this result by giving a \((1+\alpha+\varepsilon)\)-approximation algorithm for c-op and by presenting a PTAS on trees and a PTAS on Euclidean metrics. **Team Orienteering Problem (top). ** This problem is the first of a different category that considers optimizing operations of multiple vehicles. Specifically, the problem has been formalized (see Figure 7) and studied for the first time by [PERSON] et al. [34] is as follows. We are given a graph \(G=(V\cup\{s,t\},E)\) and two specific nodes \(s\) and \(t\). Notice that nodes \(s\) and \(t\) may or may not be co-located. There is an edge in \(E\) between any two nodes in \(V\cup\{s,t\}\) and there are \(K\geq 1\) vehicles to serve the nodes in \(V\). All vehicles are located at source node \(s\) initially and, for any vehicle \(k\), we have a cost function \(c_{k}:E\to\mathbb{R}^{\geq 0}\) on the edges (representing, e.g., the traveling cost of vehicle \(k\) from one vertex to another) and a cost function \(h_{k}:V\to\mathbb{R}^{\geq 0}\) on the nodes representing, e.g., the service cost of vehicle \(k\) at each vertex). We assume that \(h(s)=h(t)=0\).