# Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates

arXiv: https://arxiv.org/abs/2012.00689 · HTML: https://mlsanity.com/paper/2012.00689/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2020.

## Built on by (most cited first, 1 of 1)

- [Grounded Intuition of GPT-Vision's Abilities with Scientific Images](https://mlsanity.com/paper/2311.02069/) (2023)

## Abstract (arXiv)

We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.