Outline o Background and Motivation ● Problem statement o Representative algorithms o The greedy algorithm Revisited ● Experiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Representative Algorithms ⚫ The Greedy Algorithm Revisited ⚫ Experiments ⚫ Conclusion
Problem statement Online Minimum Bipartite Matching(OMBM) Given A set of (static)service providers w 0 Each w∈W: location l A set of (dynamic)users T' Each t E T: location Lt, arriving time at Cost Function: Any Metric Distance Function Find an online allocation m to minimize the total cost Min sum(M)=∑ t∈T,W∈W dis(t, w)st Cardinality Constraint: MminITL, Wy Real-Time Constraint(Online Scenarios Once a usert appears, a service provider must be immediately assigned to t before the next task appears Invariable Constraint (Online Scenarios): Once a user t is assigned to a service provider w, the allocation of (t, w) cannot be changed!
Problem Statement ⚫ Online Minimum Bipartite Matching (OMBM) ⚫ Given ⚫ A set of (static) service providers 𝑊 o Each 𝑤 ∈ 𝑊: location 𝒍𝑤. ⚫ A set of (dynamic) users 𝑇 o Each 𝑡 ∈ 𝑇: location 𝒍𝑡 , arriving time 𝑎𝑡 . ⚫ Cost Function: Any Metric Distance Function. ⚫ Find an online allocation 𝑀 to minimize the total cost MinSum(M)=σ𝑡∈𝑇,𝑤∈𝑊 𝒅𝒊𝒔(𝑡, 𝑤) s.t. ⚫ Cardinality Constraint: |M|=min{|T|, |W|} ⚫ Real-Time Constraint (Online Scenarios): Once a user t appears, a service provider must be immediately assigned to t before the next task appears. ⚫ Invariable Constraint (Online Scenarios): Once a user t is assigned to a service provider w, the allocation of (t, w) cannot be changed! 13
14 Evaluation for Online Algorithms Competitive Ratio(CR) ●CR= Cost of an online algorithm Cost of the corresponding offline algorithm Input Models Adversarial Model worst-Case Analysis) Minsum(m) o CRa maxVG(T, W, U)andvvev min Sum(OPT The worst bipartite graph The worst arrival order Random Order Model(Average-Case Analysis) E MinSum(m) CRpo maxvG(T, W,]) MinSum(OPT) The expectation of the total cost of all possible The worst bipartite graph arrival orders
The worst arrival order Evaluation for Online Algorithms ⚫ Competitive Ratio (CR) ⚫ 𝐶𝑅 = 𝑪𝒐𝒔𝒕 𝒐𝒇 𝒂𝒏 𝒐𝒏𝒍𝒊𝒏𝒆 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎 𝑪𝒐𝒔𝒕 𝒐𝒇 𝒕𝒉𝒆 𝒄𝒐𝒓𝒓𝒆𝒔𝒑𝒐𝒏𝒅𝒊𝒏𝒈 𝒐𝒇𝒇𝒍𝒊𝒏𝒆 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎 ⚫ Input Models ⚫ Adversarial Model (Worst-Case Analysis) o 𝐶𝑅𝐴 = 𝐦𝐚𝐱∀𝐺 𝑇,𝑊,𝑈 𝑎𝑛𝑑∀𝑣∈𝑉 𝑀𝑖𝑛𝑆𝑢𝑚(𝑀) 𝑀𝑖𝑛𝑆𝑢𝑚(𝑂𝑃𝑇) ⚫ Random Order Model (Average-Case Analysis) o 𝐶𝑅𝑅𝑂 = 𝐦𝐚𝐱∀𝐺 𝑇,𝑊,𝑈 𝔼[𝑀𝑖𝑛𝑆𝑢𝑚 𝑀 ] 𝑀𝑖𝑛𝑆𝑢𝑚(𝑂𝑃𝑇) The worst bipartite graph The worst bipartite graph The expectation of the total cost of all possible arrival orders 14
Outline o Background and Motivation ● Problem statement o Representative Algorithms o The greedy algorithm Revisited ● Experiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Representative Algorithms ⚫ The Greedy Algorithm Revisited ⚫ Experiments ⚫ Conclusion
16 Four Representative Algorithms Deterministic Algorithms Greedy [soDa 19911 Permutation [sODa 1991] o Randomized algorithms HST-Greedy [sODa 2006 HST-Reassignment [ESA 2007]
Four Representative Algorithms 16 ⚫ Deterministic Algorithms ⚫ Greedy [SODA 1991] ⚫ Permutation [SODA 1991] ⚫ Randomized Algorithms ⚫ HST-Greedy [SODA 2006] ⚫ HST-Reassignment [ESA 2007]