Problem statement Dynamic bipartite graph B=(L,R, E) R=∈N} 3 L={∈N} 6 Arrival time
Problem Statement ⚫ Dynamic bipartite graph 11 𝑩 = (𝑳,𝑹, 𝑬) 3 1 2 4 5 6 2 3 4 1 2 𝑳 = {𝒊 ∈ ℕ ∗ } 𝑹 = 𝒋 ∈ ℕ ∗ Arrival time
Problem statement 12 Dynamic bipartite graph EcL×R W(3,1)=2 3 3 4 W(4,5)=0 6 Arrival time
⚫ Dynamic bipartite graph Problem Statement 12 𝑬 ⊆ 𝑳 × 𝑹 3 1 2 4 5 2 3 4 1 𝒘(𝟑,𝟏) = 𝟐 𝒘(𝟒,𝟓) = 𝟎 6 2 Arrival time
Problem statement Dynamic bipartite graph Duration of nodes: Node 3 will vanish at time step 6 3(3 Lifetime of node 3 5)2 4(6 Arrival time
⚫ Dynamic bipartite graph Problem Statement 13 Duration of nodes: Node 3 will vanish at time step 6 3 1 2 4 5 2 3 4 1 6 5 3 1 2 4 6 Arrival time 2 Lifetime of node 3
Problem statement Dynamic bipartite graph Matching allocation: M={(3,1),(4,2),(6,5)} 3(3 5)2 4(6 Arrival time Utility score U(B,M)=2+3+2=8
⚫ Dynamic bipartite graph Problem Statement 14 3 1 2 4 5 6 2 3 4 1 2 Arrival time 6 5 3 1 2 4 Matching allocation: 𝑴 = { 𝟑, 𝟏 , 𝟒, 𝟐 , (𝟔, 𝟓)} Utility score: 𝑼 𝑩, 𝑴 = 𝟐 + 𝟑 + 𝟐 = 𝟖
Problem statement Dynamic Bipartite Graph Matching(DBGM) Problem Given dynamic bipartite graph B, where each node appears in online scenario Find matching allocation M to maximize the total utility, i c mamU(B, M) Decisions can be made freely (Without assumption of instantaneous constraint)
⚫ Dynamic Bipartite Graph Matching (DBGM) Problem ⚫ Given dynamic bipartite graph 𝑩,where each node appears in online scenario ⚫ Find matching allocation 𝑴 to maximize the total utility, i.e., 𝐦𝐚𝐱𝑴𝑼(𝑩, 𝑴) Problem Statement 15 Decisions can be made freely. (Without assumption of instantaneous constraint)