3 papers
cs.DS2025
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
Aaron Bernstein, Jiale Chen
We study the approximate maximum weight matching (MWM) problem in a fully dynamic graph subject to edge insertions and deletions. We design meta-algorithms that reduce the problem…
cs.DS2025
Stable Matching with Interviews
Itai Ashlagi, Jiale Chen, Mohammad Roghani +1
In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in m…
cs.DS2024
Entropy Regularization and Faster Decremental Matching in General Graphs
Jiale Chen, Aaron Sidford, Ta-Wei Tu
We provide an algorithm that maintains, against an adaptive adversary, a -approximate maximum matching in -node -edge general (not necessarily bipartite) und…