M. Roghani

Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and...