Mohak Goyal

Secretary Matching with Vertex Arrivals and No Rejections

Most prior work on online matching problems has been with the flexibility of keeping some vertices unmatched. We study three related online matching problems with the constraint of matching every vertex, i.e., with no rejections. We adopt a model in which vertices arrive in a uniformly random order…