# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 4 The Case \(c=2\): Algorithms and Their Analysis
### The Match-and-Assign Algorithm and Its Analysis
\begin{subarray}{c}\{i,k\},\{j\}\in c\\ (k,\{i,j\})\in M\end{subarray} }\alpha(w(d_{k},s_{i})+w(d_{k},s_{j})). \tag{28}\]  
Note that \(M_{4}\) is a minimum weight assignment in \(G_{4}=(D\cup M_{3},v_{4})\), and both \(M_{\ell}\) and \(M_{r}\) are a feasible assignment in \(G_{4}=(D\cup M_{3},v_{4})\). Thus:  
\[v_{4}(M_{4})\leq\sum_{c\in\mathbb{C}}\min\{v_{4}(M^{c}_{\ell}),v _{4}(M^{c}_{r})\}\] \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\] \[\leq\sum_{(k,\{i,j\})\in M}\frac{\alpha w(d_{k},s_{i})+\alpha w(d _{k},s_{j})}{2}.\]  
The last inequality follows from (28), and hence, (27) is proven. Lemma 7: _For any two requests \(i\) and \(j\), we have:_  
\[\max\{u_{ij},u_{ji}\}-\min\{u_{ij},u_{ji}\}\leq w(s_{i},s_{j});\]  
_and:_  
\[u_{ij}\leq 2u_{ji}.\]  
Without loss of generality, suppose \(u_{ij}\geq u_{ji}\), \(u_{ij}\leq w(s_{i},s_{j})+u_{ji}\). Since \(w(s_{i},s_{j})\leq\min\{u_{ij},u_{ji}\}\), we have \(u_{ij}\leq 2u_{ji}\) for any two requests \(i\) and \(j\). Theorem 3: _The \(\operatorname{MA}(1,u)\) is a two-approximation algorithm for \(\operatorname{CS}_{sum}\). Moreover, there exists an instance \(I\) for which \(\operatorname{cost}(\operatorname{MA}(I))=2\operatorname{cost}(M^{*}(I))\)._  
Proof: We assume w.l.o.g. that, for each \((k,\{i,j\})\in M^{*}\), \(\operatorname{cost}(k,\{i,j\})=w(d_{k},s_{i})+u_{ji}\). We have:\[\text{cost}(\text{MA}(1,u))=\sum_{(k,\{i,j\})\in\text{MA}}\min\{w(d_{k},s_{i})+u_{ij},w(d_{k},s_{j})+u_{ji}\} \tag{29}\] \[=v_{3}(M_{3})+v_{4}(M_{4})\] (30) \[\leq\sum_{(k,\{i,j\})\in M^{*}}\frac{w(d_{k},s_{i})+w(d_{k},s_{j} )+u_{ij}+u_{ji}}{2}\] (31) \[\leq\sum_{(k,\{i,j\})\in M^{*}}\frac{2w(d_{k},s_{i})+w(s_{i},s_{j })+3u_{ij}}{2}\] (32) \[\leq\frac{1}{2}\sum_{(k,\{i,j\})\in M^{*}}(2w(d_{k},s_{i})+4u_{ij})\] (33) \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]0 (34) \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]1  
Equation (29) follows from (2) and (21). Equation (30) follows from Lemma 5. Inequality (31) follows from Lemma 6. Inequality (32) follows from the triangle inequality, and \(u_{ji}\leq 2u_{ij}\) for each request pair \(\{i,j\}\in R^{2}\) based on Lemma 7. Inequality (33) follows from \(w(s_{i},s_{j})\leq u_{ij}\). Notice that \(\text{cost}(\text{MA}(I))\leq 2\text{cost}(M^{*}(I))\) is actually tight by the instance depicted in \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]2  
**Theorem 4**. : _The \(\text{MA}(1,u)\) is a \(3/2\)-approximation algorithm for \(\text{CS}_{sum,s=t}\). Moreover, there exists an instance \(I\) for which \(\text{cost}(\text{MA}(I))=3/2\)\(\text{cost}(M^{*}(I))\)._  
Proof. : \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]3 (36) \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]4 (37) \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]5 (38) \[\leq\frac{1}{2}\sum_{c\in\mathbb{C}}\left(\sum_{(k,\{i,j\})\in M^ {c}_{\ell}}v_{4}(k,\{i,j\})+\sum_{(k,\{i,j\})\in M^{c}_{r}}v_{4}(k,\{i,j\})\right)\]6 (39)  
Equation (36) follows from (20). Inequality (37) follows from Lemma 5 and 6, and \(u_{ij}=u_{ji}=w(s_{i},s_{j})\). To see that the equality may hold in \(\text{cost}(\text{MA}(I))\leq 3/2\)\(\text{cost}(M^{*}(I))\), consider the subgraph induced by the nodes \((d_{1},s_{3})\), \((s_{1},s_{2})\), and \((d_{2},s_{4})\) in Figure 3 with cars \(\{k_{1},k_{2}\}\) and requests \(\{1,2,3,4\}\).