Improved approximation schemes for the
restricted shortest path problem
David Holzmüller
January 30, 2016
2
Contents
1 Introduction 4
2 Problem Definition 5
3 Algorithm overview 5
4 Optimal Solution for the Non-Negative Integer Version 7
4.1 Solving With Positive Integers . . . . . . . . . . . . . . . . . . 7
4.2 Generalizing to Non-Negative Integers . . . . . . . . . . . . . 8
5 FPTAS for RSP 13
5.1 Scaling the Original Problem . . . . . . . . . . . . . . . . . . . 14
5.2 A Linear Approximation . . . . . . . . . . . . . . . . . . . . . 16
5.3 A Constant Approximation . . . . . . . . . . . . . . . . . . . 16
5.4 Previous Solution . . . . . . . . . . . . . . . . . . . . . . . . . 18
6 Improved FPTAS for RSP 18
6.1 Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.3 Variants of the algorithm . . . . . . . . . . . . . . . . . . . . . 21
7 Remarks 23
8 Summary 23
A German summary 25
3
Abstract
In this thesis we present several variants of an approximation
scheme for the restricted shortest path problem. This problem con-
cerns finding a shortest path with respect to one criterion while not
exceeding a length bound with respect to another criterion. After for-
mally introducing the problem, we describe the approximation scheme
by Lorenz and Raz [3]. Our algorithm then introduces additional
steps to reduce the runtime complexity from O (|E|n(1/ε+ log logn))
to O (|E|n(1/ε+ log log logn)). A variant of this algorithm yields a
complexity of O (|E|n(1/ε+ (n logn)/m)), which is a further improve-
ment for sufficiently dense graphs. Furthermore, a slight modification
leads to an O (|E|n(1/ε+ 1))-algorithm for directed acyclic graphs,
providing an arguably easier algorithm than the algorithm proposed
by Ergun et al. [1].
1 Introduction
The Restricted Shortest Path (RSP) problem concerns bicriteria path opti-
mization. It only optimizes one criterion, but the set of valid paths is restricted
by a second criterion. RSP is NP-complete, but it has a fully polynomial
time approximation scheme (FPTAS) [3], i. e. there is an algorithm finding a
(1 + ε)-approximation to the optimum whose time complexity is polynomial
in both the size of the input and 1/ε. The current best result known to us
is the algorithm proposed by Lorenz and Raz [3] with a time complexity of
O (nm(1/ε+ log log n)), where n is the number of vertices and m the number
of edges of the given graph. For directed acyclic graphs, Ergun et al. [1]
published an algorithm with time complexity O (nm(1/ε+ 1)). In this thesis,
we want to outline the algorithm by Lorenz and Raz and introduce several
techniques to reduce its time complexity, resulting in several variants. As
a side effect, we equalize the result by Ergun et al. with a slightly different
algorithm. Sections 2, 4 and 5 are mainly based on the paper by Lorenz
and Raz [3], despite differing in notation and some details. They outline
the problem, show an exact solution for integer-weighted graphs and an
approximation scheme for RSP. However, the extended exact solver in section
4.2 and the graph G−S are not relevant for the algorithm by Lorenz and Raz
— they are essential to our improved versions. Section 6 finally presents our
algorithm with a detailed analysis. Section 3 gives a brief summary of the
algorithms before they are explained in detail.
4
2 Problem Definition
The Restricted Shortest Path (RSP) problem can be defined as follows:
• Input: A directed graph G = (V,E, c, r) with two weight functions
c, r : E → R+0 . In the following, c(e) and r(e) are also referred to as the
cost and the resource consumption of an edge. Furthermore, start and
end vertices s, t ∈ V and a resource bound R ∈ R+0 . In the following,
we set n := |V | and m := |E|.
• In order to sum over all edges of a path easily, we will represent a path
by the set of its edges. This representation does not allow edges to
occur multiple times — however, since we want to find shortest paths,
relevant paths are not affected. Furthermore, we want to introduce the
set of all (acyclic) paths from s to an arbitrary vertex v ∈ V :
Pv := {{(v1, v2), . . . , (vk−1, vk)} | (v1, . . . , vk) is a path from s to v} .
Then we can define the cost of a path p ∈ Pv in G as
CG(p) :=
∑
e∈p
c(e) (2.1)
and the resource consuption of p as
RG(p) :=
∑
e∈p
r(e) . (2.2)
• A solution to the RSP problem is a path p ∈ Pt which does not exceed
the resource bound R, i. e. RG(p) ≤ R. The goal is to find a solution
p that minimizes CG(p). We refer to such a (potentially non-unique)
optimal solution as Popt(G) and to the unique optimal cost CG(Popt(G))
as Copt(G).
3 Algorithm overview
We will now give a short overview over the algorithms and ideas presented in
this thesis. In section 4, we will show that if all edges have positive integer cost,
we can solve the RSP problem exactly using a simple dynamic programming
scheme. Unfortunately, the runtime of the dynamic programming scheme
depends linearly on Copt(G), which might in turn be exponential in the size
of the input. To find an approximation for the optimal solution in reasonable
time, we can (down-)scale (i. e. divide by a scaling factor S) and then round
5
up the cost values of G. We can then run the dynamic programming scheme
on these modified cost values. This would lead to a (1 + ε)-approximation in
time O (nm(1/ε+ 1)) if we knew an appropriate scaling factor. Unfortunately,
we first need a constant approximation for Copt(G) to get such a scaling factor.
By finding the minimal value c′ such that a path p from s to t exists which
satisfies RG(p) ≤ R and c(e) ≤ c′ for all e ∈ p, we obtain L := c′ and U := nc′
as lower and upper bounds for Copt(G). To tighten these bounds, we examine
O (log n) potential scaling factors Si where Si/Si+1 = 2. By running the
dynamic programming scheme with a graph scaled by one of these Si, we can
examine whether Si is too big, acceptable or too small (in the last case we
have to stop the dynamic programming scheme after enough steps to obtain
a suitable runtime bound). Using binary search on the scaling factors, we can
then find an acceptable scaling factor in O (nm · log log n). The algorithm by
Lorenz and Raz uses this scaling factor to scale the graph and then run the
dynamic programming scheme to get a suitable path.
Our main algorithm basically adds four ideas:
• Do a linear search on i to find an acceptable Si instead of a binary
search. At first, this sounds worse since we potentially have to examine
more values for i. However, because we then only approach the target
value from one direction, we can test the big scaling factors first. This
means that we have small cost values and thus the computational effort
needed to compute the exact solution is very low for most of the values
of i examined. Ideally, doubling the scaling factor should mean that
at most half of the effort is needed. This means we could analyze
the algorithm backwards from the lowest investigated scaling factor,
doubling the scaling factor in each round. The complexity calculation
would then contain a geometric series meaning roughly that the runtime
of the last iteration is an upper bound for the cumulative runtime of all
other iterations.
• Unfortunately, doubling the scaling factor does not mean that the cost of
the scaled graph halves. The reason is that we are essentially rounding
up the scaled values to get integer values for the dynamic programming
scheme. Instead, we again deviate from the algorithm by Lorenz and
Raz by rounding down the scaled values. This modification ensures
that the requirement above holds.
• Rounding down the scaled values solves a problem, but brings up another
one. The dynamic programming scheme as used in the algorithm by
Lorenz and Raz cannot cope with edge cost values that are zero. As
Ergun et al. described, this is not a problem if the graph is acyclic.
6
To solve the problem for general graphs, we incorporate Dijkstra’s
algorithm into the dynamic programming scheme. This means that the
m in the original complexity estimation is replaced by m+ n log n, but
for graphs with many edges, this is already sufficient for an improved
runtime.
• To compensate the n log n from Dijkstra’s algorithm in sparse graphs,
we may leave the O (log log n) most expensive values of i to be searched
by the binary search algorithm already used by Lorenz and Raz. This
is the reason for the log log log n-term in the complexity of this variant
of our algorithm.
4 Optimal Solution for the Non-Negative In-
teger Version
For graphs G where the cost function c only takes positive integer values, we
can solve the RSP problem inO (m · Copt(G)) time by a dynamic programming
algorithm [2]. We will now outline this algorithm and show how it can be
extended to handle edges with cost zero. We can assume that m ∈ Ω (n), since
we can at first find the weakly connected component of s by using breadth-first
search (this works in O (m) time) and only operate on the explored subgraph
(since the equation |E| ≥ |V | − 1 holds for weakly connected graphs).
4.1 Solving With Positive Integers
We define values rk,v, k ∈ Z, v ∈ V by
rk,v := min{RG(p) | p ∈ Pv, CG(p) ≤ k} , (4.1)
i. e. rk,v denotes the minimal resource consumption amongst all paths from s
to v with cost at most k. We already know that no path with negative cost
can exist. Thus, we can conclude rk,v =∞ if k < 0. Since a path with cost 0
and resource consumption 0 exists from the start node to itself, we also know
that rk,s = 0 for all k ≥ 0. If we knew all values for rk,v, we could compute
Copt(G) using the formula
Copt(G) = min{k ∈ N0 | rk,t ≤ R} . (4.2)
Additionally, we can find an optimal path Popt(G) in O (m) time by tracing
back the cause for the value of rCopt(G),t.
7
How can we compute the remaining unknown values rk,v, i. e. for k ≥ 0
and v ∈ V \ {s}? Because a path from s to v 6= s with cost ≤ k and minimal
resource consumption must be composed of such an optimal path from s to a
node v and an edge from v to v, the equation
rk,v = min
e=(w,v)∈E
(
rk−c(e),w + r(e)
)
(4.3)
holds for all k 6= s. If c(e) ≥ 1 for all e ∈ E, this equation yields a
simple dynamic programming scheme — we can simply compute all rk,v for
k = 0, 1, . . . until rk,t ≤ R (using a standard growing-array implementation to
store these values). The runtime of this algorithm is O (m) for each row and
thus O (m · Copt(G)) in total. The cause for a value rk,v is an edge e which
minimizes the equation above. These edges can be traversed from t to s to
find out the optimal paths.
s a b c d t
(2, 1) (1, 5)
(1, 8)
(2, 7)
(1, 2) (1, 1)
(1, 2)
(1, 6)
Figure 1: Example graph G1 without zero-cost edges. Each edge e is labelled
with (c(e), r(e)).
For illustration, Figure 1 shows a Graph G1. Computing the values rk,v
for G1 corresponds to finding the cost of the shortest path to rk,v from rk′,s
for some k′ ≥ 0 in the infinite graph shown in Figure 2. The edge costs in the
original graph determine how many levels one has to go down in the infinite
graph when taking an edge. The weights of the edges are the corresponding
resource consumptions.
4.2 Generalizing to Non-Negative Integers
If we allow c(e) = 0 for some edges e, a single row cannot be computed that
easily. Here, we will use a variation of the dynamic programming approach
explained above to generate a graph G(k). Using G(k), we can then formulate a
single source shortest path (SSSP) problem whose solution entries correspond
to the row entries we want to find.
8
r−1,s r−1,a r−1,b r−1,c r−1,d r−1,t
r0,s r0,a r0,b r0,c r0,d r0,t
r1,s r1,a r1,b r1,c r1,d r1,t
r2,s r2,a r2,b r2,c r2,d r2,t
r3,s r3,a r3,b r3,c r3,d r3,t
1
1
1
8
8
8
8
5
5
5
5
7
7
7
2
2
2
2
1
1
1
1
2
2
2
2
6
6
6
6
Figure 2: Section of the infinite graph corresponding to the dynamic program-
ming scheme when applied to G1.
s a b c d t
(2, 1) (1, 5)
(1, 8)
(2, 7)
(0, 2) (0, 1)
(0, 2)
(1, 6)
Figure 3: Example graph G2 including zero-cost edges. Each edge e is labelled
with (c(e), r(e)).
9
Figure 3 shows an example for a graph with zero-cost edges. This graph G2
can again be transformed like G1 to obtain an illustration for the structure of
the dynamic programming algorithm. A section of the corresponding infinite
graph is shown in Figure 4.
r0,s r0,a r0,b r0,c r0,d r0,t
r1,s r1,a r1,b r1,c r1,d r1,t
r2,s r2,a r2,b r2,c r2,d r2,t
r3,s r3,a r3,b r3,c r3,d r3,t
r4,s r4,a r4,b r4,c r4,d r4,t
1
1
1
8
8
8
8
5
5
5
5
7
7
7
2
2
2
2
2
1
1
1
1
1
2
2
2
2
2
6
6
6
6
Figure 4: Section of the graph representing the dynamic programming scheme
for the graph G2 from Figure 3.
Since the values rk,v for fixed k might (in equation (4.3)) be dependent
on each other, we cannot use a simple traversal of the values inside a row. To
solve this problem, we introduce the weighted graphs G(k) = (V ′, E ′, γ), where
V ′ := V ∪ {vs} (vs is a new vertex), E ′ := {e ∈ E | c(e) = 0} ∪ ({vs} × V )
and
γ((a, b)) :=

r((a, b)) , (a, b) ∈ E
0 , (a, b) = (vs, s)
min{rk−c(e),v + r(e) | e = (v, b) ∈ E, c(e) > 0} , otherwise .
In our example, let us take a closer look at the situation where k = 4,
10
i. e. values for k < 4 have already somehow been computed. The already
computed values for rk,v are shown inside the nodes in Figure 5. From this
graph, we can easily derive the graph G(4)2 shown in Figure 6.
0 ∞ ∞ ∞ ∞ ∞
0 ∞ 8 10 11 ∞
0 1 8 10 11 17
0 1 6 8 9 17
r4,s r4,a r4,b r4,c r4,d r4,t
1
1
1
8
8
8
8
5
5
5
5
7
7
7
2
2
2
2
2
1
1
1
1
1
2
2
2
2
2
6
6
6
6
Figure 5: Partially computed values in the infinite graph corresponding to
G2. The edges which are relevant for building G(4)2 and thus for computing
the next row entries are highlighted in red.
The weight of an edge (vs, w) in G(k) is chosen to be the minimum resource
consumption of all paths p ∈ Pw whose cost is at most k and whose last
edge has non-zero cost. Thus, for every path from vs to a vertex u in G(k)
with weight α, there is a corresponding path from s to u in G with resource
consumption α and cost ≤ k. This shows that dG(k)(vs, u) ≥ rk,u, where
dG(k)(vs, u) is defined as the minimum weight of any path from vs to u in G(k).
Conversely, a path p from s to u in G with cost ≤ k and minimal resource
consumption can be split into a first part ending at a vertex u′ whose last
edge is an edge with non-zero cost and a second part which only consists
of zero-cost edges. The second part of the path also exists in G(k). By the
11
0 1 6 8 8 15
vs
2 1
2
0 1 6 ∞ 8 15
Figure 6: The graph G(4)2 and its shortest path weight entries corresponding
to the values r4,v.
optimality principle of shortest paths, the first part must itself have minimal
resource consumption among all paths from s to u′ with cost k. Therefore,
the weight of the edge (vs, u′) in G(k) must be the resource consumption of the
first part of p. But this shows dG(k)(vs, u) ≤ rk,u and thus dG(k)(vs, u) = rk,u.
Because of this, we can use Dijkstra’s algorithm with a fibonacci heap to
compute all rk,v-values for a fixed k, i. e. a row of the dynamic programming
table, in time O (m+ n log n). Consequently, the running time for the overall
algorithm is now O ((m+ n log n) · (1 + Copt(G))) (the 1 is necessary because
Copt(G) might be zero). Note that we do not have to build the whole graph
G(k) to run the algorithm although we would be able to do so without
increasing the computational complexity of the overall algorithm.
If G is a directed acyclic graph, we can even solve the SSSP-problem in
O (m) time. If G is an undirected graph with im(r) ⊆ N+, we can use an
algorithm of Thorup (which assumes constant-time multiplication) and obtain
the same time complexity [4]. If we only assume G to fulfill im(r) ⊆ N0 (G
does not have to be undirected), we can use the priority queue data structure
proposed by van Emde Boas et al. and obtain a runtime in O (m+ n log logR)
[5]. To simplify dealing with these special cases, we propose the following
definition:
Definition 1. Let G be a graph as defined in section 2. Then we define
fG(n,m) := m if G is acyclic or undirected with positive integer resource
values. This means that we can replace the cost function of G by an arbitrary
modified cost function c′ with im (c′) ⊆ N0 and still compute one row of our
dynamic programming scheme for G in O (m). Otherwise, if im(r) ⊆ N0, we
define fG(n,m) := m + n · min{log n, log logR}. In all other cases, we set
fG(n,m) := m+ n log n. Thus, we can compute the exact solution for such a
12
modified G in time O (fG(n,m)(1 + Copt(G))).
Algorithm 1 shows the rough structure of the algorithm. Additionally,
an iteration limit l is included, providing the possibility to test whether
Copt(G) ≤ l. Using the examinations from above, we obtain the following
lemma.
Lemma 2. Let G be defined as above. Given any modified graph G′ =
(V,E, c′, r) with c′ satisfying im(c′) ⊆ N0 and an iteration limit l ∈ N0 ∪{∞},
Algorithm 1 finds out
• an optimal path and the optimal cost Copt(G′) if Copt(G′) ≤ l
• the fact that Copt(G′) > l otherwise
in time O (fG(n,m) · (1 + min{l, Copt(G′)})). If 0 6∈ im(c′), the time complex-
ity bound O (m · (1 + min{l, Copt(G′)})) can be achieved.
Algorithm 1 Algorithm for solving the RSP Problem exactly, including an
optional iteration limit l
function ExactRSP(G = (V,E, c, r), s ∈ V, t ∈ V,R ∈ R+0 , l ∈ N0∪{∞})
for k from 0 to l do
Compute rk,v for all v
if rk,t ≤ R then
Trace the optimal path p back from rk,t
return (p, k)
end if
end for
return (⊥,∞)
end function
5 FPTAS for RSP
Since all parts of the algorithm by Lorenz and Raz [3] are used in our algorithm
and we want to use a slightly different formulation, we will explain it here.
Their algorithm finds a (1 + ε)-approximation to the RSP problem in time
O (nm (1/ε+ log log n)). This means that the algorithm will find a solution
pε to the RSP problem with CG(pε) ≤ (1 + ε)Copt(G). We may assume that
Copt(G) > 0 since we can easily check this condition at the beginning by
running Dijkstra’s algorithm on all edges with cost zero, finding the smallest
13
possible resource consumption on this subgraph. Running the algorithm on
a graph with an optimal cost of zero would cause a division by zero — this
special case can also easily be detected after running the linear approximation
described in section 5.2.
5.1 Scaling the Original Problem
Given the graph G and a scaling factor S ∈ R+, we can build the graphs G−S
and G+S with integer costs on their edges by replacing the cost function c of
G by c−S and c+S , respectively. These two functions are defined as follows:
c−S (e) :=
⌊
c(e)
S
⌋
c+S (e) :=
⌊
c(e)
S
⌋
+ 1 .
Notice that while the former graph has lower edge cost, the latter graph is
guaranteed to have positive integer edge cost and thus enables us to use the
algorithm from section 4.1.
Now let us analyze the behavior of the optimal solutions of these scaled
graphs in the original graph. Concerning the approximation quality of an
optimal scaled graph solution, we can derive1
CG(Popt(G+S )) =
∑
e∈Popt(G+S )
c (e)
= S · ∑
e∈Popt(G+S )
c(e)
S
≤ S · ∑
e∈Popt(G+S )
(⌊
c(e)
S
⌋
+ 1
)
≤ S · ∑
e∈Popt(G)
(⌊
c(e)
S
⌋
+ 1
)
≤ S · ∑
e∈Popt(G)
(
c(e)
S
+ 1
)
≤ Copt(G) + nS
=
(
1 + nS
Copt(G)
)
Copt(G) . (5.1)
1A similar bound can be derived for G−S , but it will not be used for the algorithms
described here.
14
In addition, we want to analyze the estimation quality in the scaled graphs.
It should be clear that
Copt(G+S ) ≥
Copt(G)
S
(5.2)
and
Copt(G−S ) ≤
Copt(G)
S
. (5.3)
Since the cost of each edge in G+S differs exactly by one from the cost of the
same edge in G−S and the optimal path consists of at most n− 1 edges, we
also know that
Copt(G+S ) < Copt(G−S ) + n
(5.3)
≤ Copt(G)
S
+ n (5.4)
and similarly
Copt(G−S ) > Copt(G+S )− n
(5.2)
≥ Copt(G)
S
− n . (5.5)
Using these equations, we see that the approach using G−S takes
O
(
fG(n,m) · (1 + Copt(G−S ))
)
⊆ O
(
fG(n,m) ·
(
1 + Copt(G)
S
))
(5.6)
time, while using G+S leads to a runtime in
O
(
m · Copt(G+S )
)
⊆ O
(
m ·
(
n+ Copt(G)
S
))
. (5.7)
You might notice that for big scaling factors S, more specifically for those
satisfying Copt(G−S ) ∈ o (n/ log n), we should use G−S because it leads to a
faster runtime. Conversely, for smaller scaling factors, the use of G+S might be
advantageous. The combination of these two variants is a key to the improved
runtime of our algorithm.
By equation (5.1), we know that if we choose
S ≤ εCopt(G)
n
, (5.8)
the exact solution of G+S yields a (1 + ε)-approximation for the original
problem. If we chose S := εCopt(G)/n and solved the RSP problem for G+S
exactly, the runtime complexity would be O (nm(1 + 1/ε)) as obtained from
equation (5.7).
Unfortunately, we cannot use this approximation directly because we need
to know Copt(G) to be able to compute the scaling factor S. But if we were able
15
to determine a lower bound L for Copt(G) satisfying L ≥ Copt(G)/d for some
constant d, we could use S := εL/n and still obtain a (1 + ε)-approximation
with the same runtime complexity. Assuming that we have an algorithm
ConstantBounds which computes such a constant-approximation lower
bound (possibly together with an upper bound), algorithm 2 shows how to
obtain the desired (1 + ε)-approximation.
Algorithm 2 Algorithm finding a (1+ε)-approximation for the RSP problem
function ApproxRSP(G = (V,E, c, r), s ∈ V, t ∈ V,R ∈ R+0 , ε ∈ R+)
(L,U) := ConstantBounds(G, s, t, R)
S := ε · L/n
(p′, c′) := ExactRSP(G+S , s, t, R)
return (p′, CG(p′))
end function
5.2 A Linear Approximation
As a first step towards a constant approximation we will derive an efficiently
computable linear approximation algorithm for the RSP problem. At first,
we can sort the edges of G by their cost in ascending order. This can be done
in time O (m logm). Let e1, . . . , em be these sorted edges. We are then able
to compute the graphs Gi := (V,Ei, c, r) where Ei := {e1, . . . , ei}. For any i,
we can check in time O (m+ n log n) whether there is a path from s to t in
Gi whose resource consumption is no more than R by executing Dijkstra’s
algorithm on (V,Ei, r). Thus, using binary search, we can find the smallest i
for which such a path exists in time O ((m+ n log n) logm) — let us call it
i∗.
Ignoring the trivial case s = t, we now know that any solution path p to
the problem cannot only use edges with lower cost than c(ei∗). Therefore,
L := c(ei∗) is a lower bound for Copt(G). On the other hand, we know that
there is a solution to the original problem only consisting of edges from
Ei∗ . It follows that U := n · c(ei∗) is an upper bound for Copt(G). This is
summarized in algorithm 3. Since the runtime of this algorithm is in O (nm)
and thus does not affect the overall time complexity, we will neglect it in
further considerations.
5.3 A Constant Approximation
To find a constant approximation, we would like to get an approximation with
known approximation quality using a value c′ = Copt(G+S ) for some scaling
16
Algorithm 3 Algorithm finding a linear approximation for the RSP problem
function LinearBounds(G = (V,E, c, r), s ∈ V, t ∈ V,R ∈ R+0 )
(e1, . . . , em) := edges sorted by ascending cost
Find i∗ by using binary search with Dijkstra on (Gi)1≤i≤m
return (c(ei∗), n · c(ei∗))
end function
factor S. Using (5.2) and (5.4), we see that Sc′ ≥ Copt(G) and
Sc′
Copt(G)
≤ Sc
′
Sc′ − Sn =
c′
c′ − n . (5.9)
For example, if c′ ≥ 2n, we have c′/(c′ − n) ≤ 2 and thus Sc′ is a
2-approximation upper bound for Copt(G).
As we have shown at the end of section 5.1, all we have to do to find a
constant approximation is to find a scaling factor S such that c′ = Copt(G+S )
is at least 2n. To limit the computation time needed for computing that
optimum, we also require c′ ≤ 5n. Both requirements are certainly fulfilled
if (Copt(G)/S) ∈ [2n, 4n] (this follows from the inequalities in section 5.1).
Given lower and upper bounds (L,U) for Copt(G), we know that this is true
for some S where
L
2n ≤ S ≤
U
2n . (5.10)
Because 4n = 2 · 2n, it suffices to consider a subset of all possible values
for S such that the quotient of two consecutive values in this subset does not
exceed 2 (i. e., the gaps between the values are not too big). Thus, we only
need to consider the values
Si :=
U
2n · 2
−i (5.11)
for i ∈ {0, . . . , dlog2(U/L)e}. Executing the statement
(p′, c′) := ExactRSP(G+Si , s, t, R, 5n) (5.12)
lets us distinguish three cases in time O(mn):
• If c′ < 2n, we know that Si is too big.
• If c′ =∞, we know that Si is too small.
• If 2n ≤ c′ ≤ 5n, we know that L := Sic′/2 is a lower bound and
U := Sic′ is an upper bound for Copt(G).
17
Thus, we can again use binary search to find a number i∗ such that Si∗
is a desired scaling factor. Because we know that i∗ ∈ {0, . . . , dlog2(U/L)e},
this computation runs in time O (mn log log(U/L)). Algorithm 4 shows the
structure of this approach.
Algorithm 4 Algorithm finding a constant approximation for the RSP
problem from arbitrary lower and upper bounds
function ConstBounds(G = (V,E, c, r), s ∈ V, t ∈ V,R ∈ R+0 , L ∈
R+, U ∈ R+)
Compute values Si from L and U
Find i∗ by using binary search on Si
S := Si∗
(p′, c′) := ExactRSP(G+S , s, t, R,∞)
return (Sc′/2, Sc′)
end function
5.4 Previous Solution
The algorithm by Lorenz and Raz [3] uses the result of the linear approximation
from section 5.2 as bound inputs for the constant approximation algorithm
shown in section 5.3. This leads to a runtime in O (nm log log n), yielding an
overall time complexity of
O
(
nm
(1
ε
+ log log n
))
(5.13)
for the (1 + ε)-approximation scheme.
6 Improved FPTAS for RSP
In this section, we want to propose a O (log n)-approximation for the RSP
problem with a time complexity of O (nm) which directly leads to an im-
proved FPTAS with a runtime complexity of O (nm(1/ε+ log log log n)).
Furthermore, we introduce a variant of this approximation which can find a
2-approximation for RSP in time O (nfG(n,m)).
6.1 Basic Algorithm
In section 5.3, we have seen that by analyzing G+Si for different values of i,
we can find a 2-approximation for Copt(G). Now we will consider the same
18
values Si, i ∈ {0, . . . , dlog2(U/L)e}, but instead analyze G−Si because it has
lower edge cost. This enables us to run a linear search on the Si-values in
reasonable time. The concrete algorithm is desribed as algorithm 5. This
algorithm contains a parameter b to trade off approximation quality against
runtime complexity. It traverses the values Si until the graph G−Si has an
optimal cost > b. Based on b, U and the last value of i, it then returns a
valid approximation for Copt(G), as we will prove in the next section.
Algorithm 5 Algorithm using linear search to find bounds for the RSP
problem
1: function LSBounds(G = (V,E, c, r), s ∈ V, t ∈ V,R ∈ R+0 , b ∈ N+)
2: (L,U) := LinearBounds(G, s, t, R)
3: Compute values Si from L and U
4: for i = 0, 1, 2, . . . do
5: S := Si
6: (p′, c′) := ExactRSP(G−S , s, t, R, b)
7: if c′ =∞ then
8: if i = 0 then
9: return (Sb, U)
10: else
11: return (Sb, 2S(b+ n))
12: end if
13: end if
14: end for
15: end function
6.2 Analysis
First, we want to show that the bounds found by this algorithm are indeed
correct. Obviously, U is a correct upper bound as we have explained in section
5.2. When the algorithm finds that c′ = ∞, we know that Copt(G−S ) > b.
Thus, we have
b · S < Copt(G−S ) · S ≤ Copt(G) . (6.1)
Finally, if the algorithm reaches line 11, the value of c′ in the previous iteration
must have been at most b. Using the bounds from section 5.1, we obtain
b ≥ Copt(G−Si−1) ≥
(
Copt(G)
Si−1
− n
)
. (6.2)
Since we know that Si−1 = 2Si, it follows that
Copt(G) ≤ (b+ n)Si−1 = 2(b+ n)Si . (6.3)
19
Now that we have shown the correctness of the algorithm, we can analyze
the quality of the approximation, concretely the quotient U/L, for arbitrary
values of b.
Lemma 3. For the values U and L returned by Algorithm 5, the estimation
U/L ∈ O (1 + n/b) holds.
Proof. We have to distinguish two cases:
• The algorithm terminates in line 9. Then,
U
L
= U
S0b
= U · 2n
Ub
= 2n
b
. (6.4)
• The algorithm terminates in line 11. In this case, we obtain
U
L
= 2S(b+ n)
Sb
= 2 + 2n
b
. (6.5)
We can therefore conclude that U/L ∈ O (1 + n/b).
The last part of our analysis concerns the time complexity of the algorithm.
By Lemma 2, we know that the runtime of ExactRSP(G′, s, t, R, b) lies
in O (fG(n,m) · (1 + min{b, Copt(G′)})). Because of this, we can bound the
runtime h(i) of iteration i from above by
h(i) ≤ AfG(n,m) · (1 + min{b, Copt(G−Si)}) +D (6.6)
for some constants A,D ∈ R+. Let i∗ be the value of i in the last iteration.
If b ≤ n, we can derive the estimation
i∗ ≤ dlog2 ne (6.7)
similar to our analysis of the binary search bounds in section 5.3.2
Now, we can take our final step towards the running time of the algorithm.
Lemma 4. If b ≤ n, the time complexity of algorithm 5 is
O (fG(n,m) · (1 + b+ log n)) .
2Note that the assumption b ≤ n was only made for simplicity. If we dropped the
assumption, we could derive i∗ ≤ ⌈log2 ( b+n2 )⌉ and Lemma 4 would still hold.
20
Proof. Obviously, T (i∗) := ∑i∗i=0 h(i) describes the runtime of the loop in the
algorithm. If i∗ = 0, we have
T (i∗) =
i∗∑
i=0
h(i) ≤ AfG(n,m) · (1 + b) +D ∈ O (fG(n,m) · (1 + b+ log n)) .
If instead i∗ > 0, we know that the previous scaling factor Si∗−1 led to a
graph with optimal cost less than or equal to b. Since for all e ∈ E
c−2S(e) =
⌊
c(e)
2S
⌋
≤ 12
⌊
c(e)
S
⌋
, (6.8)
we conclude Copt(G−Sj−1) ≤ Copt(G−Sj)/2 for every j > 0. Iterating this
inequality, we obtain
Copt(G−Si∗−1−k) ≤ 2−kCopt(G−Si∗−1) ≤ 2−kb (6.9)
for every 0 ≤ k ≤ i∗− 1. Using the shorthand F := fG(n,m), this leads us to
the estimation
T (i∗) =
i∗∑
i=0
h(i)
≤
(
i∗−1∑
i=0
AF (1 + Copt(G−Si)) +D
)
+ (AF (1 + b) +D)
(6.9)
≤
(
i∗−1∑
i=0
AF2−(i∗−1−i)b
)
+ (AF +D) · i∗ + (AF · (1 + b) +D)
≤ AFb
i∗−1∑
j=0
2−j
+ (AF +D)(1 + i∗) + AFb
≤ AFb
 ∞∑
j=0
2−j
+ (AF +D)(1 + i∗) + AFb
= 3AFb+ (AF +D)(1 + i∗)
(6.7)
≤ 3AFb+ (AF +D) (2 + log2 (n))
∈ O (fG(n,m) · (1 + b+ log n)) ,
which proves the claim.
6.3 Variants of the algorithm
Because we are able to choose the parameter b in the algorithm above freely,
there are several possibilities of usage. At first, we want to present our
improved general FPTAS.
21
Corollary 5. A O (log n)-approximation for RSP can be computed with a
runtime in O (nm). Using this approximation as an input for the constant
approximation algorithm from section 5.3, the overall algorithm has a time
complexity of O (nm(1/ε+ log log log n)).
Proof. We will show that algorithm 5 computes the desired O (log n)-appro-
ximation with the mentioned complexity when using
b := max
{
1,
⌊
n
log n
⌋}
. (6.10)
Using Lemma 3, we see that
U
L
∈ O (1 + n/b) = O (1 + log n) = O (log n) . (6.11)
According to Lemma 4, the runtime of the algorithm lies in
O (fG(n,m) · (1 + b+ log n)) ⊆ O
(
(m+ n log n) ·
(
1 + nlog n + log n
))
= O
(
n
(
m
log n + n
))
and thus, since m ≥ n− 1, also in O (nm).
The complexity of this algorithm can be improved in any case where
fG(n,m) ∈ O (m), i. e. for graphs where the exact algorithm with zero-
cost edges runs in time O (m · (1 + Copt(G))). As mentioned in section 4.2,
these graphs comprise directed acyclic graphs and, assuming constant-time
multiplication, undirected graphs where im(r) ⊆ N+.
Corollary 6. A O (1)-approximation for RSP can be computed with a runtime
in O (n · fG(n,m)). Using this approximation, the overall algorithm has a
time complexity of O (nm(1/ε+ fG(n,m)/m)).
Proof. We will show that algorithm 5 computes the desired O (1)-approxima-
tion with the mentioned complexity when using
b := n . (6.12)
By Lemma 3, we have
U
L
∈ O (1 + n/b) = O (1 + 1) = O (1) . (6.13)
According to Lemma 4, the runtime of the algorithm lies in
O (fG(n,m) · (1 + b+ log n)) ⊆ O (fG(n,m) · (1 + n+ log n))
= O (n · fG(n,m)) .
22
7 Remarks
Throughout this thesis, we use the notation O (f) for functions f : Rn → R,
which we assume to be defined as
O (f) := {g : Rn → R | ∃A,D ∈ R : g ≤ Af +D} . (7.1)
Furthermore, we have some more ideas that might help to further improve
the runtime of our algorithm:
• If the time needed to compute one row of the dynamic programming
scheme could be improved to O(m) for graphs with zero-cost edges,
we would instantly get the desired O (mn(1 + 1/ε)) runtime for the
approximation scheme.
• The runtime of this row computation only has to be improved if we
have n/ log n ≤ Copt(G−S ) ≤ n and m ∈ o (n log n). Both assertions
indicate that there are possibly fewer and/or smaller cycles in the graph
generated for Dijkstra’s algorithm than for denser graphs and higher
scaling factors.
• Since the zero-cost edges do not change during one execution of the
dynamic programming scheme, we might be able to speed up the
SSSP computation by doing a precomputation at the beginning of the
dynamic programming scheme. This precomputation may take up to
O (mn/ log log n) time. In addition, one could try to exploit the fact
that in successive iterations in the linear search algorithm, no zero-cost
edges are ever added to the scaled graph.
• We only have to apply Dijkstra’s algorithm to the strongly connected
components of the graph from section 4.2. The acyclic part of its
structure can be handled efficiently.
• After having computed the O (log n)-approximation, one might want
to establish randomized rounding to obtain a Monte-Carlo approxima-
tion algorithm. Unfortunately, although it might work for “average”
graphs, there are counterexamples where it is unlikely to find a good
approximation.
8 Summary
In this thesis, we were able to improve the runtime of the approximation
scheme to O (nm(1/ε+ log log log n)). Unfortunately, we did not find a pos-
sibility to reduce the runtime complexity to the somewhat more aesthetic
23
O (nm(1/ε+ 1)) for all graphs, although we enlarged the types of graphs for
which this complexity can be achieved. As we indicated in the last section,
many ideas can be found to modify our algorithm. Assessing their use requires
precise analysis and often brings up even more variants to be reviewed. The
restricted shortest path problem thus remains an interesting challenge for
future research.
References
[1] F. Ergun, R. Sinha, and L. Zhang. An improved FPTAS for restricted
shortest path. Information Processing Letters, 83(5):287–291, 2002.
[2] R. Hassin. Approximation schemes for the restricted shortest path problem.
Mathematics of Operations research, 17(1):36–42, 1992.
[3] D. H. Lorenz and D. Raz. A simple efficient approximation scheme
for the restricted shortest path problem. Operations Research Letters,
28(5):213–219, 2001.
[4] M. Thorup. Undirected single-source shortest paths with positive integer
weights in linear time. Journal of the ACM (JACM), 46(3):362–394, 1999.
[5] P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation
of an efficient priority queue. Mathematical Systems Theory, 10(1):99–127,
1976.
24
A German summary
Das „Restricted Shortest Path“-Problem ist ein NP-hartes bikriterielles Op-
timierungsproblem. Eingabe ist ein Graph G = (V,E, c, r), dessen Kanten
durch nichtnegative Funktionen c und r ein Kosten- und ein Ressourcenwert
zugewiesen ist. Ziel ist es, den bezüglich der Gesamtkosten CG(p) günstigsten
Pfad p von s ∈ V nach t ∈ V zu finden, dessen Ressourcensumme RG(p)
einen Grenzwert R nicht übersteigt. Dabei bezeichnet n die Anzahl der Kno-
ten und m die Anzahl der Kanten des Graphen. Mithilfe von dynamischer
Programmierung kann ein solcher optimaler Pfad Popt(G) gefunden werden,
falls der Graph ganzzahlige Kostenwerte besitzt. Die Laufzeit dieses Lösungs-
verfahrens hängt linear von der Anzahl m der Kanten von G und den Kosten
Copt(G) = CG(Popt(G)) des optimalen Pfads ab. Um die Abhängigkeit von
den Kosten des Pfades zu vermeiden, kann die Kostenfunktion eines Graphen
G skaliert und gerundet werden. Dabei wird abhängig vom Skalierungsgrad
eine hinsichtlich der Pfadkosten mehr oder weniger gute Approximation für
den optimalen Pfad gefunden. Die Hauptkomplexität des Problems steckt
darin, einen geeigneten Skalierungsfaktor zu finden.
Der Algorithmus von Lorenz und Raz findet zuerst auf einfache Weise
eine O (n)-Approximation für Copt(G). Anschließend werden basierend auf
dieser Approximation O (log n) potenzielle Skalierungsfaktoren mit binärer
Suche durchsucht, bis ein geeigneter Skalierungsfaktor gefunden wird. Da jeder
Suchschritt eine Zeitkomplexität von O (nm) hat, liegt die Gesamtkomplexität
für diese Suche bei O (nm log log n). Eine (1 + ε)-Approximation kann damit
mit einer Zeitkomplexität von O (nm(1/ε+ log log n)) erhalten werden.
Der neue Ansatz, der in dieser Bachelorarbeit vorgestellt wird, ist in einer
Zeit in O (nm) in der Lage, die Anzahl der mit binärer Suche zu durchsu-
chenden Skalierungsfaktoren auf O (log log n) und für manche Graphen sogar
auf 0 einzuschränken. Damit verringert sich die Laufzeit des Approximations-
algorithmus von O (nm(1/ε+ log log n)) auf O (nm(1/ε+ log log log n)) bzw.
O (nm(1/ε+ 1)). Dieser Ansatz basiert auf vier Ideen:
• Es wird eine lineare Suche im Gegensatz zur binären Suche verwendet.
Diese muss zwar mehr Skalierungsfaktoren durchsuchen, benötigt für die
meisten Faktoren aber erheblich weniger Zeit, sodass sich letztendlich
in der Abschätzung eine geometrische Reihe ergibt.
• Um diese Laufzeitreduktion durch die lineare Suche gewährleisten zu
können, werden die Kosten beim Skalieren abgerundet statt aufgerundet.
• Die durch das Abrunden auftretenden Kanten mit Nullkosten müssen
im exakten Lösungsalgorithmus speziell behandelt werden, dafür wird
25
im Allgemeinen der Algorithmus von Dijkstra verwendet.
• Da der Algorithmus von Dijkstra die Zeitkomplexität für Graphen mit
wenigen Kanten erhöht, können bei diesen Graphen nur die billige-
ren Skalierungsfaktoren mit dieser Methode durchsucht werden. Es
verbleiben dann O (log log n) Skalierungsfaktoren, die mit der bereits
bekannten Suchtechnik durchsucht werden können.
In dieser Bachelorarbeit werden das Problem und der Algorithmus von
Lorenz und Raz ausführlich vorgestellt. Außerdem wird der erwähnte neue
Ansatz zur Verbesserung der Laufzeit vorgestellt und ausführlich analysiert.
26