# Safe Approximation--An Efficient Solution for a Hard Routing Problem
## 3 The Method of Safe Approximation  
The various above referenced solutions tend to be rather complicated, which is certainly not helpful for real-life applications, in particular for large, complex networks. Our approach for providing a more practical solution to the unsplittable flow problem based on the following idea. We \"cut down\" a small part of the solution space by slightly re ducing the edge capacities. In other words, we exclude solutions that are close to saturating some edges, as explained below. Let \(V_{i}\) be the given flow demand of the \(i^{\text{th}}\) connecting path. We normalize these demands such that \(V_{i}\leq 1\) for every \(i\). Let \(C_{j}\) be the capacity of edge \(j\). The graph is assumed directed and the edges are numbered from 1 through \(m\). Recall that a feasible solution of the problem is a set of \(s_{i}-t_{i}\) (directed) paths, one for each \(i\), satisfying the edge capacity constraints. The latter means that on each edge \(j\) the sum of the \(V_{i}\) values of those paths that traverse the edge does not exceed \(C_{j}\). As mentioned earlier, deciding whether a feasible solution exist at all is a hard (**NP**-complete) problem. On the other hand, not all feasible solutions are equally good from a practical viewpoint. For example, if a route system in a network saturates or nearly saturates some links, then it is not preferable because it is close to being overloaded. For this reason, let us assign a parameter \(0<\rho_{j}<1\) to each edge \(j\), such that \(\rho_{j}\) will act as a _safety margin_ for the edge. More precisely, let us call a feasible solution a _safe solution_ with parameters \(\rho_{j},\ j=1,\ \dots,\ m\), where \(m\) is the number of edges, if it uses at most \(\widehat{C}_{j}=\rho_{j}C_{j}\) capacity on edge \(j\). The parameter \(\rho_{j}\) will be close to 1 in the cases that are interesting to us. Now, the appealing thing is that if we restrict ourselves to only those cases when a safe solution exists, then the hard algorithmic problem becomes solvable by a relatively simple randomized polynomial time algorithm. With very high probability, the algorithm finds the _exact optimum_ in polynomial time, whenever there exists a safe solution. We call this approach _safe approximation_. The price is that we exclude those cases when a _feasible_ solution might still possibly exists, but there is no _safe_ solution. This means, in these cases all feasible solutions are undesirable, because they all make some edges nearly saturated. In these marginal cases the algorithm may find no solution at all. Our approach constitutes a new avenue to approximation, in the sense that instead of giving up finding an exact solution, we rather restrict the search space to a (slightly) smaller one. When, however, the algorithm finds _any_ solution, then it provides the _exact_ (not just approximate) optimum. Let us choose the _safety margin_\(\rho_{j}\) for edge \(j\) in a graph of \(m\) edges as  
\[\rho_{j}=1-(\mathbf{e}-1)\sqrt{\frac{\ln 2m}{C_{j}}}\approx 1-1.71\sqrt{\frac{ \ln 2m}{C_{j}}}, \tag{1}\]  
where \(C_{j}\) is the capacity of edge \(j\), In denotes the natural logarithm \(\log_{e}\), and \(\mathbf{e}\approx 2.718\dots\) is [PERSON]'s number (the base of the natural logarithm). Note that \(\rho_{j}\) tends to 1 with growing \(C_{j}\), even if the graph also grows, but \(C_{j}\) grows faster than the logarithm of the graph size, which is very reasonable (note that doubling the number of edges will only increase the natural logarithm by less than 1). For example, if an edge has capacity \(C_{j}=1000\) units (measured in relative units, such that the maximum path flow demand is 1), and the graph has \(m=200\) edges, then \(\rho_{j}\approx 0.87\). Now, we outline how the algorithm works. First, we describe a continuous multicommodity flow relaxation. **Continuous multicommodity flow relaxation** Let \(V_{i}\) be the given flow demand of the \(i^{\text{th}}\) connecting path, with source node \(s_{i}\) and target node \(t_{i}\).