## 3 Computational Problems and Algorithms
### Maximum Prize Problems
**Capacitated Team Orienteering Problem (c-top). ** c-top is a generalization of top in which we also consider node demands \(r:V\rightarrow\mathbb{N}\) and a capacity bound \(C\) for each walk (vehicle). For such generalization, formalized in Figure 8, [PERSON] and [PERSON] [33] designed a \((1-e^{\frac{1}{\alpha}})\)-approximation algorithm, where \(\alpha\) is an approximation factor for c-op, under the following assumptions:  
* each vehicle has the same budget \(B\) and the same capacity \(C\);
* for each vehicle, the cost of each vertex is \(0\), the cost of each edge is the same and the prize of each vertex is the same. It is worth pointing out that [PERSON] et al. [37] proved that a \(\beta\)-approximation algorithm for c-top can be turned into a \(2\beta\)-approximation algorithm for the _Capacitated Team  
Figure 7: Formalization of top. _Orientteering with Split Deliveries_, a variant of c-top in which a node demand can be served by several walks (vehicles). _Problem_: Capacitated Team Orienteering Problem (c-top)  
_Input_: an undirected graph \(G=(V,E)\), for any vertex \(v_{i}\in V\) a prize function \(u_{i}:K\to\mathbb{R}^{\geq 0}\) and a demand \(r(v_{i})\in\mathbb{N}\), a set of \(K\) vehicles, for any vehicle \(k\in[K]\), an edge cost function \(l_{k}:E\to\mathbb{R}^{\geq 0}\), a node cost function \(h_{k}:V\to\mathbb{R}^{\geq 0}\), a budget \(B_{k}\in\mathbb{R}^{>0}\) and a capacity \(C_{k}\in\mathbb{N}\), and specific nodes \(s,t\in V\). _Feasible Solution_: a walk \(P_{st}^{k}\) for any vehicle \(k\in[K]\) s.t. for any \(k\in[K]\), \(w(P_{st}^{k})=\sum_{e\in E(P_{st}^{k})}l_{k}(e)+\sum_{e\in V(P_{st}^{k})}h_{k} (0)\leq B_{k}\) and \(r(P_{st}^{k})=\sum_{e\in V(P_{st}^{k})}r(0)\leq C_{k}\). _Goal_: \(\sum_{v_{i}\in\bigcup_{k}^{k}P_{k}}u_{i}(v_{k})\) maximized. A summary of the results on op and its variants is given in Table 1. In such summary we have \(\varepsilon>0\) while \(\alpha\) and \(\alpha^{\prime}\) are approximation factors to op and its directed version, respectively. Parameter \(\beta\) is an approximation factor to c-op while \(OPT\) is the cost of the optimal solution to the problem. Moreover, \(L_{max}\) and \(L_{min}\) are the longest and shortest time windows, respectively. Finally, \(\gamma\) is an approximation ratio for d-tsp with a constant number of deadlines (currently the best known factor is \(\gamma=3\) by [PERSON] and [PERSON] [26]). Note that a \((a,b)\)-bicriteria approximation algorithm to optw is the one which has a \(b\)-approximation factor and violates the time windows by a factor of \(a\). **Reoptimization of the Metric Deadline Traveling Salesman Problem (md-tsp). ** In the Metric Deadline Traveling Salesman Problem (md-tsp), we are given a _metric_ graph \(G=(V,E)\) (i.e., a graph where costs on the edges satisfy the triangle inequality), a specific node \(s\in V\), and the goal is to find a Hamiltonian cycle, starting at \(s\), having minimum cost and that visits each vertex \(v\) before its deadline \(D(v)\), assuming that there exists at least one Hamiltonian cycle \(P\) in which each vertex is visited before its deadline (see Figure 9 for details on the formalization). The time of visit \(t_{p}(v)\) of a vertex \(v\) is given by the sum of the costs of the edges of the sub-path of the Hamiltonian cycle starting at \(s\) and terminating at \(v\). The problem has interest itself with respect to applications, but perhaps the md-tsp has been investigated more from a re-optimization perspective, where one is given a good (even optimal) solution to the problem and some modifications that affect the original input, and the objective is to rearrange the given solution to obtain a provably good new solution for the new input, with a minimal number of operations.