## 3 Computational Problems and Algorithms
### Maximum Prize Problems  
**Orienteering Problem (op). ** In this first basic problem formalization, we are given a graph \(G=(V,E)\) with \(n=|V|\) vertices and \(m=|E|\) edges, weighted with a cost function \(l:E\to\mathbb{R}^{\geq 0}\) on the edges and a prize function \(\pi:V\to\mathbb{R}^{\geq 0}\) on the vertices, a budget \(B\in\mathbb{R}^{>0}\) and two distinguished nodes \(s,t\), and we are asked to find a walk \(P_{st}\) from \(s\) to \(t\) that: (i) satisfies the budget constraints, i.e., the sum of the costs of the edges in the walk is smaller than or equal to \(B\); (ii) maximizes a collected prize for the walk, where the collected prize of a walk is given by the sum of the prizes associated to the vertices in the walk. More formally, the problem can be described as in Figure 3.  
Due to the plethora of applications that the problem finds, the literature on algorithms for finding approximate solutions with guarantees is ample. Specifically, [PERSON] et al. [17] gave the first constant factor approximation algorithm for op with approximation ratio of 4 when \(s=t\) and showed that no polynomial-time approximation algorithm can achieve a factor better than \(\frac{1481}{480}\) to op. In the same paper, the authors also showed that op is APX-hard  
Figure 3: Formalization of op. while [PERSON] et al. [18] improved the bound of [PERSON] et al. by designing an algorithm with approximation ratio of 3 when \(s=t\). Moreover, [PERSON] et al. [19] proposed a \(2+\varepsilon\) approximation algorithm that works for any positive constant \(\varepsilon\) while [PERSON] and [PERSON] [20] designed, via LP-rounding, a 3-approximation algorithm when \(s=t\). The solution given by [PERSON] et al. [21], instead, is a 2-approximation algorithms that solves OP when \(s\) and \(t\) are not given in advance. Finally, [PERSON] and [PERSON] [22] gave a polynomial-time approximation scheme (PTAS) when the points lie in a constant dimensional Euclidean metric. **Orienteering Problem with Time Windows (optw). ** In this problem variant (formalization is given in Figure 4), the goal is to find a walk from a starting node to an ending node that visits a set of vertices with the maximum profit within their time windows respecting a given budget \(B\). Given a walk \(P_{uw}\) from \(u\) to \(v\), for any \(z\in V(P_{uw})\), let \(t_{P}(u,z)\) denote the time taken (distance) to reach \(z\in V(P_{uw})\) from \(u\) along \(P_{uw}\). Note that, the optw problem is also known as the Repairman problem, (Speeding) Delivery Man problem [23], Time Window Prize Collecting problem [24], and Prize-Collecting TSP with Time Windows [25]. [PERSON] et al. [18] gave an \(\mathcal{O}(\log^{2}(n))\) approximation algorithm for optw when \(s=t\). They also proposed an \(\mathcal{O}(\log(1/\varepsilon))\) approximation algorithm for optw when \(s=t\) if exceeding the deadlines by a factor of \(1+\varepsilon\) is permitted. [PERSON] and [PERSON] [26] gave a constant factor approximation algorithm for the special case of this problem when the number of time windows is a constant. Given an \(\alpha\) approximation for OP, [PERSON] et al. [19] proposed an \(\mathcal{O}(\alpha\cdot\max\{\log OPT,\log\frac{t_{\max}}{L_{min}}\})\) approximation for optw, where: (i) \(OPT\leq n\) is the number of vertices visited by an optimal solution; (ii) \(L_{max}\) and \(L_{min}\) are the lengths of the longest and shortest time windows, respectively. [PERSON] et al. [25] provided two approximation algorithms for optw on a line. The first algorithm is an 8-approximation algorithm, where its complexity time is \(\mathcal{O}(n^{2})\). The second one is a \((4+\varepsilon)\)-approximation algorithm and its complexity time is \(\mathcal{O}(n^{8}/\varepsilon)\). [PERSON] et al. [27] provided a 4-approximation algorithm for optw with unitary length time windows on a line whose complexity time is \(\mathcal{O}(n^{2})\).