eldorado.tu-dortmund.de/server/api/core/bitstreams/cf5ba697-aacf-4258-9644-d0de0763b019/content
1, . . . , v2,ℓ, v1,i+1) of p2. It holds that f(p̂2) ri f(p1) since
fv1,i+1,j(p̂2) = fv2,ℓ,j(p2) + wj((v2,ℓ, v1,i+1))
≤ ri · fv1,i,j(p̂1) + wj((v1,i, v1,i+1))
≤ ri · fv1,i+1,j(p1),
for all 1 ≤ j ≤ k, and [...] ri · fv1,i,j(p̂1)
holds for all 1 ≤ j ≤ k. Using i ≤ n− 2 and r < c1/(n−2), we get
ri · fv1,i,j(p̂1) ≤ rn−2 · (n− 1) · wmax < c · (n− 1) · wmax.
9
v1,0
v2,0
v1,1 · · · v1,i−1
v2,1 · · · v2,ℓ−1
v1,i
v2,ℓ [...] c1/(n−2). Further, 1 ≤ i ≤ n − 2 and P ⊆ PATH≤n−1(1, ·) with f(P ) ri f(PATH≤i(1, ·)). Consider a path
p1 = (1, v1,1, . . . , v1,i, v1,i+1) ∈ PATHi+1(1, ·).
Then there is a path p2 = (1, v2,1, . . . , v2,ℓ) ∈ …
