Problem statement Evaluation metric Competitive ratio in adversarial model U(B,M CR=minG Opt ( B) Theoretical quarantee of Offline optimum an online algorithm in worst case
⚫ Evaluation Metric ⚫ Competitive ratio in adversarial model 𝑪𝑹 = 𝐦𝐢𝐧𝑩 𝑼(𝑩,𝑴) 𝑶𝒑𝒕(𝑩) Problem Statement 16 Theoretical guarantee of an online algorithm in worst case Offline optimum
Outline e background and motivation ● Problem statement ° Our Solutions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 17
Our framework 18 We propose an adaptive batch-based framework 6 Cumulate the Match all the dynamically coming nodes in the batch nodes into a batch 5 3(3 4 Adaptively 5)2 adjust the size of batch 6 Time of arrival
⚫ We propose an adaptive batch-based framework Our framework 18 3 1 2 4 5 6 2 3 4 1 2 Time of arrival 6 5 3 1 2 4 Cumulate the dynamically coming nodes into a batch Adaptively adjust the size of batch Match all the nodes in the batch
Our framework We propose an adaptive batch-based framework 6 Challenge 1: How optimal is an adaptive batch based framework in theory? Challenge 2: How to implement an optimal strategy to split batches adaptively? size of batch 6 Time of arrival
Adaptively adjust the size of batch Time of arrival ⚫ We propose an adaptive batch-based framework Our framework 19 3 1 2 4 5 2 3 4 1 2 6 5 3 1 2 Cumulate the dynamically coming nodes into a batch Match all the nodes in the batch Challenge 1: How optimal is an adaptive batchbased framework in theory? 4 6 Challenge 2: How to implement an optimal strategy to split batches adaptively?