13 C=2
u v 𝜏=3 c=2 13 t=9
13 13 items split into g=13/2= 7 groups First group reached v at time tT-3 Last group reached v at time t3+g-1=9 Discrete Model Default for this talk ° Wpeople, Capacity c integral, Transit timeτ All edge transit times integral Requires W/c+t-1 time to move everyone from u to v Continuous model W units of non-quantized fluid Fluid flows continuously cis rate: amount that can enter e in one unit of time Requires w/C+ T-1 time to move all fluid from tov
u v 𝜏=3 c=2 13 t=9 • 13 items split into g = ⌈13/2⌉ = 7 groups • First group reached v at time t= 𝜏=3 • Last group reached v at time t= 3 +g -1=9 Discrete Model • W people, Capacity c integral, Transit time 𝜏 • All edge transit times integral • Requires ⌈W/c ⌉+ 𝜏-1 time to move everyone from u to v Continuous Model • W units of non-quantized fluid. Fluid flows continuously • c is rate: amount that can enter e in one unit of time • Requires W/c+ 𝜏-1 time to move all fluid from u to v Default for this talk
Outline Dynamic flow networks Congestion in Dynamic Flows Evacuation flows Problem definitions Known results EXample algorithm 1: k-Sink Evacuation on a Path Example algorithm 2: 1-sink Min-Max Regret Evacuation on a Path with uniform capacity Open problems
Outline • Dynamic Flow Networks • Congestion in Dynamic Flows • Evacuation Flows • Problem Definitions • Known Results • Example Algorithm 1: k-Sink Evacuation on a Path • Example Algorithm 2: 1-sink Min-Max Regret Evacuation on a Path with uniform capacity • Open Problems
Congestion Effects A major complication with dynamic flows is that they ntroduce congestion effects that can slow down transport time 16 19
19 Congestion Effects u w v 𝜏1=3 c1=8 𝜏2=5 c2=3 16 9 A major complication with dynamic flows is that they introduce congestion effects that can slow down transport time
Congestion Effects 16 τ1=3C1=8 T2=5c2=3
20 Congestion Effects u w v 𝜏1=3 c1=8 𝜏2=5 c2=3 16 9