# Safe Approximation--An Efficient Solution for a Hard Routing Problem
## 3 The Method of Safe Approximation
**Step 3**_Feasibility Check and Repetition_  
Having found a system of paths in the previous step, check whether it is a feasible solution (i.e., it can carry the flow demand for each path within the capacity bounds). If so, then halt, else repeat from Step 2. If after repeating \(r\) times (\(r\) is a fixed parameter) none of the runs are successful then declare \"No solution is found\" and halt. It is clear from the above description that the algorithm has practically feasible complexity, since the most complex part is the linear programming. Note that while Step 2 is repeated \(r\) times, the linear program in Step 1 needs to be solved only once. The correctness of the algorithm is shown in the following theorem. Theorem 1: _If a safe solution exists, then the algorithm finds a feasible solution with probability at least \(1-2^{-r}\)._  
Proof: Since a safe solution is also a feasible solution of the multicommodity flow relaxation, therefore, if there is no flow solution in Step 1, then no safe solution can exist either. Step 2 transforms the flow solution into paths. To see that they are indeed paths, observe that looping cannot occur in the randomized branching procedure, because if a circle arises on the way, that would mean a circle with all positive flow values for a given commodity, which could be canceled from the flow of that commodity, thus contradicting to the fact that the linear program finds a flow in which the sum of edge flows is minimum, according to the objective function (5). Furthermore, since looping cannot occur, we must reach the destination via the procedure in at most \(n\) steps, where \(n\) is the number of nodes. Now a key observation is that if we build the paths with the described randomization between the \(i^{\text{th}}\) source-destination pair, then the _expected value_ of the load that is put on any given edge by these paths will be exactly the value of the \(i^{\text{th}}\) commodity flow on the link. This follows from the fact that the branching probabilities are flow-proportional. From the above we know that the total expected load of an edge, arising form the randomly chosen paths, is equal to the total flow value on the edge. What we have to bound is the deviation of the _actual_ load from this expected value. Let \(F_{j}\) be the flow (=expected load) on edge \(j\). This arises in the randomized procedure as  
\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]3  
where \(X_{i}\) is a random variable that takes the value 1 if the \(i^{\text{th}}\) path (i.e., the type-\(i\) flow) contributes to the edge load, otherwise it is 0. The construction implies that these random variables are independent, whenever \(j\) is a fixed edge and \(i\) runs over the different flow types. Now consider the random variable  
\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]4By (6), we have \(\mathrm{E}(\Psi_{j})=F_{j}\). The probability that the actual random value \(\Psi_{j}\) deviates form its expected value by \(F_{j}\) by more than a factor of \(\delta\) can be bounded by the tail inequality found in [16], which is a variant of the Chernoff-Hoeffding bound:  
\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]5  
It can be calculated from this [16] that if we want to guarantee that the bound does not exceed a given value \(\epsilon>0\), then it is sufficient to satisfy  
\[\sum_{j\in\text{In}(v)}x_{j}^{i} =\sum_{k\in\text{Out}(v)}x_{k}^{i}.\]6  
Let us choose \(\epsilon=1/(2m)\).