## 3 Computational Problems and Algorithms
### Maximum Prize Problems
Then, the cost \(w(P^{k}_{st})\) of a simple path \(P^{k}_{st}\) from \(s\) to \(t\) is given by:  
\[w(P^{k}_{st})=\sum_{v\in V(P^{k}_{st})}h_{k}(v)+\sum_{e\in E(P^{k}_{st})}c_{k}( e).\]  
For any vehicle \(k\), let \(B_{k}\) denote the cost budget of vehicle \(k\), meaning that \(w(P^{k}_{st})\leq B_{k}\). Moreover, for any vertex \(v_{i}\), let \(n_{i}\) be the number of vehicles among \(K\) vehicles that serve \(v_{i}\). For any vertex \(v_{i}\), let \(u_{i}:K\to\mathbb{R}^{\geq 0}\) be a non-decreasing sub-modular profit function, where \(u_{i}(n_{i})\) represents the profit that we accumulate after serving vertex \(v_{i}\) with \(n_{i}\) vehicles. **Problem**: Capacitated Orienting Problem (c-op)  
_Input_: an undirected graph \(G=(V,E)\), a prize function \(\pi:V\to\mathbb{R}^{\geq 0}\), a cost function \(l:E\to\mathbb{R}^{\geq 0}\), a node demand function \(r:V\to\mathbb{N}\), specific nodes \(s,t\in V\), a budget \(B\in\mathbb{R}^{>0}\) and a capacity \(C\in\mathbb{N}\). _Feasible Solution_: a walk \(P_{st}\) s.t. \(l(P_{st})=\sum_{e\in E(P_{st})}l(e)\leq B\) and \(r(P_{st})=\sum_{v\in V(P_{st})}r(e)\leq C\). _Goal_: \(\pi(P_{st})=\sum_{v\in V(P_{st})}\pi(v)\) maximized. Figure 5: Formalization of d-tsp. Figure 6: Formalization of c-op. The objective in top, in \(G\), is to find \(K\) paths \(P_{st}^{1},p_{st}^{2},\ldots,P_{st}^{K}\) for \(K\) vehicles each starting from node \(s\) and ending at \(t\), such that the profit sum of the nodes served by the \(K\) vehicles, i.e., \(\sum_{\alpha_{k}\in\bigcup_{k}^{k}p_{st}^{k}}u_{i}(\alpha_{k})\), is maximized, subject to that the cost \(w(P_{k})\) of each path \(P_{st}^{k}\) for vehicle \(k\) is no greater than its cost budget \(B_{k}\), i.e., \(w(P_{st}^{k})\leq B_{k}\) with \(1\leq k\leq K\). That is, we seek:  
\[\max\sum_{u\in\cup_{k}^{k}P_{st}^{k}}u_{i}(\alpha_{k})\]  
subject to  
\[w(P_{st}^{k})\leq B_{k},1\leq k\leq K\]  
[PERSON] et al. [34] showed that There is a \(1/(1-e^{-\alpha})\)-approximation algorithm for top, where \(e\) is the base of the natural logarithm, and \(\alpha\) is an approximation factor to op. Prior to these works, a simpler variant of top was studied by [PERSON] et al. [17]. In such variant, for any two vehicles \(k,j\in[K]\), any edge \(e\in E\), and any node \(v\in V\), we have that: (i) \(l_{k}(e)=l_{j}(e)\) (i.e., the cost of any edge is the same for all vehicles); (ii) \(\pi_{k}(v)=\pi_{j}(v)=\pi(v)\) (i.e., the prize of any node is the same for all vehicles) and the prize function \(\pi\) is additive; (iii) \(B_{k}=B_{j}\) (i.e., all vehicles have identical budget); (iv) \(h_{k}(v)=0\) (i.e., for any vehicle \(k\in[K]\), the cost of any vertex is \(0\)). Furthermore, all the vehicles have the same starting point \(s\), and the end point is arbitrary. [PERSON] et al. [17] called this problem _Multi-Path Orienteering_ and showed that any \(\alpha\) approximation for op when \(s=t\), can be translated into a \(1/(1-e^{-\alpha})\) approximation for Multi-Path Orienteering. [PERSON] et al. [17] also showed that their algorithm has a factor of \(\alpha+1\) when the starting point of each vehicle is arbitrary in Multi-Path Orienteering. [PERSON] et al. [35] studied a variant of Multi-Path Orienteering in the case where each vehicle needs to find a tour (i.e., \(s=t\)), each node has a cost, and for any two tours \(P_{k},P_{j}\), \(V(P_{k})\cap V(P_{j})=\{s\}\). The goal is to find \(K\) tours so that the minimum total prize among all tours is maximized, i.e., \(\max\min_{v}\pi(P)\). They called this problem _max-min_ orienteering and showed that any \(\alpha\)-approximation algorithm for op results in an \((\alpha+2)\)-approximation for _max-min_ orienteering. To complete the overview, it is worth mentioning the work by [PERSON] et al. [36] who focused on top when \(s=t\), the prize function for each vehicle is additive and each vertex should be visited once. Such variant has been named _monitoring reward maximization_ problem and in [36] a corresponding 3-approximation for the problem has been presented.