Fully Online Matching

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=AOnAw6OaDCg


Duration: 52:03
10,963 views
18

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors' arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc.

See more at https://www.microsoft.com/en-us/research/video/fully-online-matching/



Other Videos By Microsoft Research


2018-09-20Fireside Chat with Susan Athey
2018-09-18Fireside Chat with Cynthia Dwork
2018-09-18Towards a Theory for Sample-efficient Reinforcement Learning with Rich Observations
2018-09-17Large-scale Models of Consumer Choice and Counterfactual Inference
2018-09-14EdgeNet: A Lightweight Scalable Edge Cloud
2018-09-14Telling Stories: Analyzing Text to Understand Personality, Social behavior, and Narratives
2018-09-14LSH-Sampling Breaks the Computation Chicken-and-Egg Loop in Adaptive Stochastic Gradient Estimation
2018-09-14The Matching Problem in General Graphs is in Quasi-NC
2018-09-14Super-Human AI for Strategic Reasoning
2018-09-13Network Topologies for Large-scale Datacenters: It's the Diameter, Stupid!
2018-09-13Fully Online Matching
2018-09-12Playing to the crowd and other social media mandates with Dr. Nancy Baym
2018-09-11Exploring the Reliability of the NYC Subway System
2018-09-11Tech Showcase: Confidential AI: Secure Multi-Party Artificial Intelligence
2018-09-11Tech Showcase: FarmBeats: Empowering Farmers with Low-Cost Digital Agriculture Solutions
2018-09-11Tech Showcase: High-Fidelity Network Validation for Cloud Scale Networks
2018-09-11Tech Showcase: Optical Networking Innovation at Microsoft
2018-09-11Tech Showcase: Platform for Situated Intelligence
2018-09-11Tech Showcase: Private Compute
2018-09-07AI Infrastructure and Tools
2018-09-07A Cross-modal Audio Search Engine based on Joint Audio-Text Embeddings


Tags:
microsoft research