online bipartite matching, in batches
This post follows up on the Online Bipartite Matching series, specifically building on the primal-dual techniques discussed in Part II. Recently, I attended a talk by Yiding Feng at SJTU that introduced a fascinating application of these techniques in a broader context, as detailed in their paper. Batching and Optimal Multi-stage Bipartite Allocations Yiding Feng and Rad Niazadeh In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching....