香港科技大学：Graph Evacuation Problems

Graph Evacuation Problems Mordecai golin Hong Kong UST CRM June 2015

Graph Evacuation Problems Mordecai GOLIN Hong Kong UST CRM June, 2015

Joint work with Guru Prakash Arumugam John augustine Di chen Siu-Wing Cheng Yuya higashikawa Naoki Katoh Guangun Ni asan力Sana Yinfen地

Joint Work with • Guru Prakash Arumugam • John Augustine • Di Chen • Siu-Wing Cheng • Yuya Higashikawa • Naoki Katoh • Guanqun Ni • Bing Su • Prashanth Srikanthan • Yinfeng Xu 2

Outline ynamIc 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 3

Evacuating graphs Graph g=(V, E) represents structure Vertices are rooms, Edges are hallways Vertices are Buildings, Edges are roads Edge weight Te is transit time on edge Edge capacity Ce is " width Special vertices(sinks)are emergency exits In case of emergency, want to evacuate everybody to exits as quickly as possible Problem: Design good Evacuation Protocols Often Approached via Dynamic Flow Networks

Evacuating Graphs • Graph G=(V,E) represents structure • Vertices are rooms, Edges are Hallways • Vertices are Buildings, Edges are roads • Edge weight 𝜏e is transit time on edge • Edge capacity ce is “width” • Special vertices (sinks) are emergency exits • In case of emergency, want to evacuate everybody to exits as quickly as possible • Problem: Design Good Evacuation Protocols • Often Approached via Dynamic Flow Networks

Dynamic Flow Networks G=(,E丿 Edges have travel times Te and capacities ce Distinguished source s and sink t Max Flow Over Time Problem (input 7) How much flow can be pushed from s to t in time T? Ford Fulkerson (1958) Not polynomial( Constructs Static Max-Flow each timestep) Quickest Flow Problem (input w How quickly can W items be moved from s to t? Burkard, Dlasks and Klinz (1993) Strongly Polynomial (uses parametric search) Quickest Transhipment Problem Like QF Problem but Multiple Sources/Sinks (with fixed supply/demands) Hoppe T ardos(2000) Strongly polynomial(but uses sub modular optimization)

Dynamic Flow Networks • G=(V,E) • Edges have travel times 𝜏e and capacities ce • Distinguished source s and sink t • Max Flow Over Time Problem (input T) How much flow can be pushed from s to t in time T? • Ford Fulkerson (1958) • Not polynomial (Constructs Static Max-Flow each timestep) • Quickest Flow Problem (input W) How quickly can W items be moved from s to t? • Burkard, Dlasks and Klinz (1993) • Strongly Polynomial (uses parametric search) • Quickest Transhipment Problem Like QF Problem but Multiple Sources/Sinks (with fixed supply/demands) • Hoppe & Tardos (2000) • Strongly Polynomial (but uses sub modular optimization) s t

Edges have Capacities Original flow model is static. Doesnt model time Time required is function of both transit times and capacities Ce is edge capacity("width") At most Ce people can enter edge e=lu, vin one time unit They travel together as a group on e If more than Ce people at U, remainder need to wait to enter e Te is time for one group to traverse edge Start with W people at u How much time does take them all to reach v? C=2

Edges have Capacities • Original Flow Model is static. Doesn’t model time • Time required is function of both transit times and capacities • ce is edge capacity (“width”) • At most ce people can enter edge e=(u,v) in one time unit. They travel together as a group on e • If more than ce people at u, remainder need to wait to enter e • 𝜏e is time for one group to traverse edge • Start with W people at u How much time does take them all to reach v? 13 u v 𝜏=3 c=2

t=0

13 u v 𝜏=3 c=2 t=0

2 C=2

11 u v 𝜏=3 c=2 t=1 2

t=2 9 2 2 C=2

9 u v 𝜏=3 c=2 t=2 2 2

t=3 2 C=2

7 u v 𝜏=3 c=2 t=3 2 2 2