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