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