Let L be some class of standard latency functions. Let I = (G = (V,A), (la)a=A,...

Transcribed Image Text:

Let L be some class of standard latency functions. Let I = (G = (V,A), (la)a=A, (Si, ti)iɛ[k], (ri)iċ[k]) be a selfish routing instance with latency functions (la)a€A € Lª. Define al as the instance that we obtain from I if we scale all demands by a ≥ 1, i.e., al = (G, (la)a=A, (Si,ti)i≤[k], (αri)i=[k]). Recall the definition of w(L) as defined in the Lecture Notes and assume that 0 ≤ w(L) < 1. Let f be a Nash flow of I and let f* be an optimal flow of al with a := (1 + w(L)). Show that C(f) <C(f*). Hint: Consider the flow x = 1f* and use the variational inequality. Let L be some class of standard latency functions. Let I = (G = (V,A), (la)a=A, (Si, ti)iɛ[k], (ri)iċ[k]) be a selfish routing instance with latency functions (la)a€A € Lª. Define al as the instance that we obtain from I if we scale all demands by a ≥ 1, i.e., al = (G, (la)a=A, (Si,ti)i≤[k], (αri)i=[k]). Recall the definition of w(L) as defined in the Lecture Notes and assume that 0 ≤ w(L) < 1. Let f be a Nash flow of I and let f* be an optimal flow of al with a := (1 + w(L)). Show that C(f) <C(f*). Hint: Consider the flow x = 1f* and use the variational inequality.

Answer rating: 100% (QA)

Here is the proof Let f be a Nash flow of I and f be an optimal flow of al where a 1 wL Con... View the full answer