# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 4 The Case \(c=2\): Algorithms and Their Analysis
### The Combined Algorithm and Its Analysis  
The \(\mathrm{CA}_{sum}\) runs the \(\mathrm{MA}(1,u)\) and \(\mathrm{TA}(v_{1})\) and then outputs the better of the two solutions. We now state the main result for \(\mathrm{CS}_{sum}\). Theorem 6: _The \(\mathrm{CA}_{sum}\) is a two-approximation algorithm for \(\mathrm{CS}_{sum}\). Moreover, there exists an instance \(I\) for which \(\mathrm{cost}(\mathrm{CA}_{sum}(I))=2\mathrm{cost}(M^{*}(I))\)._  
Figure 4: A worst-case instance of the \(\mathrm{MA}(2,\mu)\) for \(CS_{lat,s=t}\). Figure 3: A worst-case instance for the \(\mathrm{CA}_{sum}\) of \(\mathrm{CS}_{sum,s=t}\). Proof. : It is obvious that, as \(\text{cost}(\text{CA}_{sum})=\min\{\text{cost}(\text{MA}(1,u)),\text{cost}(\text{ TA}(v_{1}))\}\), Theorems 1 and 3 imply that the \(\text{CA}_{sum}\) is a two-approximation algorithm for \(\text{CS}_{sum}\). We now provide an instance for which this ratio is achieved. Consider the instance \(I\) depicted in Figure 2. This instance has two cars \(D=\{k_{1},k_{2}\}\) with car locations \(\{d_{1},d_{2}\}\) and four requests \(R=\{1,2,3,4\}\). Locations corresponding to distinct vertices in Figure 2 are at Travel Time 1. Observe that an optimal solution is \(M^{*}(I)=\{(k_{1},\{1,3\}),(k_{2},\{2,4\})\}\) with \(\text{cost}(M^{*}(I))=2\). Note that \(M^{*}_{R}=\{\{1,3\},\{2,4\}\}\). Let us now analyze the performance of the \(\text{MA}(1,u)\) and \(\text{TA}(v_{1})\) on instance \(I\). Based on the \(u_{ij}\) values as defined in (20), the \(\text{MA}(1,u)\) can find, in the first step, matching \(M_{3}=\{\{1,2\},\{3,4\}\}\) with \(v_{3}(M_{3})=v_{3}(M^{*}_{R})=3\). Then, no matter how the second step assigns the request pairs to cars (since two cars stay at the same location), the total cost of \(\text{MA}(1,u)\) will be four. The \(\text{TA}(v_{1})\) may assign Requests 1 and 2 to Car 1 and Requests 3 and 4 to Car 2 since:  
\[v_{1}(\{(k_{1},1),(k_{1},2),(k_{2},3),(k_{2},4)\})=v_{1}(\{(k_{1},1),(k_{1},3),(k_{2},2),(k_{2},4)\})=6.\]  
Thus, the total cost of the \(\text{TA}(v_{1})\) is four. To summarize, the instance in Figure 2 is a worst-case instance for the \(\text{CA}_{sum}\). Theorem 4.1.: _The \(\text{CA}_{sum}\) is a \(7/5\)-approximation algorithm for \(\text{CS}_{sum,s=t}\). Moreover, there exists an instance 1 for which \(\text{cost}(\text{CA}_{sum}(I))=7/5\)\(\text{cost}(M^{*}(I))\)._  
Proof. : We assume w.l.o.g. that, for each \((k,\{i,j\})\in M^{*}\), \(\text{cost}(k,\{i,j\})=w(d_{k},s_{i})+u_{ij}\). We have:  
\[5\text{cost}(\text{CA}_{sum})\leq 4\text{cost}(\text{MA}(1,u))+ \text{cost}(\text{TA}(v_{1})) \tag{46}\] \[\leq 4(v_{3}(M_{3})+v_{4}(M_{4}))+v_{1}(M_{1})\] (47) \[\leq\sum_{(k,\{i,j\})\in M^{*}}\big{(}4w(d_{k},s_{i})+3w(d_{k},s _{j})+4w(s_{i},s_{j})\big{)}\] (48) \[\leq\sum_{(k,\{i,j\})\in M^{*}}\big{(}7w(d_{k},s_{i})+7w(s_{i},s _{j})\big{)}\] (49) \[=\sum_{(k,\{i,j\})\in M^{*}}7\ \text{cost}(k,\{i,j\})\] (50) \[=7\ \text{cost}(M^{*}) \tag{51}\]  
Inequality (47) follows from Lemma 5 and inequality (7). Inequality (48) follows from Lemmas 2 and 6. Inequality (49) follows from the triangle inequality. Inequality (50) follows from \(\text{cost}(k,\{i,j\})=w(d_{k},s_{i})+u_{ij}\). We now provide an instance for which this ratio is achieved. Consider the instance \(I\) depicted in Figure 3:0 This instance has four cars \(\{k_{1},k_{2},k_{3},k_{4}\}\) with car locations \(\{d_{1},d_{2},d_{3},d_{4}\}\) and eight requests \(R=\{1,2,\dots,8\}\). If two points are not connected by an edge, their travel time equals five. Observe that an optimal solution is  
Figure 3:1  
with \(\text{cost}(M^{*}(I))=10\). Note that \(M^{*}_{R}=\{\{1,3\},\{2,4\},\{5,6\},\{7,8\}\}\). Let us now analyze the performance of \(\text{MA}(1,u)\) and \(\text{TA}(v_{1})\) on instance \(I\). Based on the \(u_{ij}\) values as defined in (20), the \(\text{MA}(1,u)\) can find, in the first step, matching \(M_{3}=\{\{1,2\},\{3,4\},\{5,6\},\{7,8\}\}\) because \(v_{3}(M_{3})=v_{3}(M^{*}_{R})=8\).