# Safe Approximation--An Efficient Solution for a Hard Routing Problem
## 3 The Method of Safe Approximation
We refer to \(i\) as the _type_ of the flow. For each such type, and for each edge \(j\), assign a non-negative variable \(x_{j}^{i}\), representing the amount of type-\(i\) flow on edge \(j\). The flow model is then expressed by the following constraints:  
1. **Capacity constraints** For every edge \(j\) \[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\] (2)  
The meaning of (2) is that the flow on edge \(j\), summed over all types, cannot be more than the capacity of the edge, reduced by the safety margin. 2. **Flow conservation** For every node \(v\), let \(\text{In}(v)\) denote the set of incoming edges of \(v\). Similarly, let \(\text{Out}(v)\) be the set of outgoing edges of \(v\). Then write for every flow type \(i\) and for every node \(v\), except \(s_{i}\) and \(t_{i}\): \[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\] (3) The meaning of (3) is that for every flow type \(i\), the type-\(i\) flow is conserved at every node, except its source \(s_{i}\) and destination \(t_{i}\). By conservation we mean that the total incoming type-\(i\) flow to \(v\) is equal to the total outgoing type-\(i\) flow from \(v\). 3. **Source constraints** For every flow type \(i\) (which has its source at node \(s_{i}\)): \[\sum_{j\in\text{Out}(s_{i})}x_{j}^{i}=V_{i}.\] (4) The meaning of (4) is that source \(s_{i}\) should emit \(V_{i}\) amount of type-\(i\) flow. Now we can describe our algorithm. The used notations are summarized in Table 1.  
**Procedure**  
**Step 1**_Multicommodity flow relaxation_  
Solve the following linear program:  
\[\min\sum_{i}\sum_{j}x_{j}^{i} \tag{5}\]  
Subject to  
\[\sum_{i}x_{j}^{i} \leq \rho_{j}\text{C}_{j}\hskip 56.905512 pt(\forall j)\] \[\sum_{j\in\text{In}(v)}x_{j}^{i} = \sum_{k\in\text{Out}(v)}x_{k}^{i}\hskip 56.905512 pt(\forall i,\ \forall v\
eq s_{i},t_{i})\] \[\sum_{j\in\text{Out}(s_{i})}x_{j}^{i} = V_{i}\hskip 56.905512 pt(\forall i)\] \[x_{j}^{i} \geq 0\hskip 56.905512 pt(\forall i,j).\]  
In case there is no feasible solution, then declare \"no safe solution exists\" and halt. \begin{table}
\begin{tabular}{c c} \hline \hline
**Notations** & **Definitions** \\ \hline \(m\) & Number of edges \\ \(n\) & Number of vertices \\ \(V_{i}\) & Given flow demand of the \(i^{\text{th}}\) connecting path \\ \(s_{i}\) & Source node \\ \(t_{i}\) & Target node \\ \(\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]0\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]1\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]2\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]3\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]4 \text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]5\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]6\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]7\text{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]8{\[\sum_{i}x_{j}^{i}\leq\rho_{j}C_{j}.\]9\text{\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]0\text{\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]1\text{\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]2{}{{}{{}{{}{}{{}{{}{}{{}{}{{}{}{}{}{{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{{}{}{}{}{}{}{{}{}{}{}{}{  
**Step 2**_Path Creation via Random Walk_  
For each source-destination pair \(s_{i},t_{i}\) find a path via the following randomized procedure. Start at the source \(s_{i}\) and take the next node such that it is drawn randomly among the successor neighbors of the source, with probabilities proportional to the \(i^{\text{th}}\) commodity flow values on the edges from \(s_{i}\) to the successor neighbors in the directed graph. Continue this in a similar manner--at each node choose the next one among its successor neighbors randomly, with probabilities that are proportional to the \(i^{\text{th}}\) commodity flow values. Finally, upon arrival at \(t_{i}\), we store the found \((s_{i},t_{i})\) path.