research
∙
04/05/2023
A Structural and Algorithmic Study of Stable Matching Lattices of Multiple Instances
Recently MV18a identified and initiated work on the new problem of under...
share
research
∙
07/22/2021
Online Bipartite Matching and Adwords
A simple and optimal online algorithm for online bipartite matching, cal...
research
∙
01/19/2021
The General Graph Matching Game: Approximate Core
The classic paper of Shapley and Shubik <cit.> characterized the core of...
research
∙
12/07/2020
A Proof of the MV Matching Algorithm
The Micali-Vazirani (MV) algorithm for maximum cardinality matching in g...
research
∙
10/12/2020
An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs
We prove that a fractional perfect matching in a non-bipartite graph can...
research
∙
01/29/2019
Matching is as Easy as the Decision Problem, in the NC Model
We give an NC reduction from search to decision for the problem of findi...
research
∙
01/29/2019
A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching
The difficulty of obtaining an NC perfect matching algorithm has led res...
research
∙
03/30/2018
Finding Stable Matchings that are Robust to Errors in the Input
Given an instance A of stable matching, let B be the instance that resul...
research
∙
02/19/2018
A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts
We study a natural generalization of stable matching to the maximum weig...
research
∙
01/31/2018
