Adaptive Dynamic Bipartite Graph Matching A Reinforcement Learning Approach Yansheng Wang 1, Yongxin Tong1, Cheng Long2, Pan Xu3, Ke Xu1, Weifeng Lv 1 1 Beihang University 2 Nanyang Technological University 3 University of Maryland, College Park ERSIT 南洋埋工大學 4 NANYANO 9 TECHNOLOGICA UNIVERSIT RYLA
Adaptive Dynamic Bipartite Graph Matching: A Reinforcement Learning Approach Yansheng Wang 1 , Yongxin Tong 1 , Cheng Long 2 , Pan Xu 3 , Ke Xu 1 , Weifeng Lv 1 1 Beihang University 2 Nanyang Technological University 3 University of Maryland, College Park
Outline e background and motivation ● Problem statement ° Our so| utions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 2
Outline o Background and Motivation ● Problem statement ° Our so| utions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 3
Background Bipartite graph matching 3 Solved by the Hungarian method 4 in polynomial time 6 Harold w, Kuhn Traditional applications Assignment problem, vehicle scheduling problem, etc. Perform well in offline scenarios
⚫ Bipartite graph matching ⚫ Traditional applications ⚫ Assignment problem, vehicle scheduling problem, etc. ⚫ Perform well in offline scenarios Background 4 3 1 2 4 5 6 2 3 4 1 2 Solved by the Hungarian method in polynomial time Harold W. Kuhn
Background Emergence of online scenarios Transportation Medical Economic Taxi-hailing, Mutual blood donation, Two-sided market, Ride sharing, Kidney exchange,… Crowdsourcing, 回 UNOS amazon THOO!! UBER ANSWERS UNITED NETWORK FOR ORGAN SHARING mechanical turk Online matching is more and more important
⚫ Emergence of online scenarios Background 5 Transportation Medical Economic Taxi-hailing, Ride sharing, … Mutual blood donation, Kidney exchange, … Two-sided market, Crowdsourcing, … Online matching is more and more important