# Online Many-to-one Matching

## Offline Problem

I have a graph $$\mathcal{G} = (\mathcal{D} \cup \mathcal{A}, \mathcal{E})$$. Each edge $$e \in \mathcal{E}$$ between the two vertex sets $$\mathcal{D}$$ and $$\mathcal{A}$$ has an associated weight $$w_e$$. Also, each vertex in $$\mathcal{A}$$ has a quota $$Q$$ i.e. each vertex in $$\mathcal{A}$$ can match with at most $$Q$$ vertices in $$\mathcal{D}$$. I need to find a matching between $$\mathcal{D}$$ and $$\mathcal{A}$$, such that the sum of weights is maximized.

## Online Version

The vertices $$\mathcal{D}$$ arrive one-by-one and upon arrival, all the corresponding weights to the vertex set $$\mathcal{A}$$ is revealed. On each arrival, I need to match the vertex in $$\mathcal{D}$$ with a vertex in $$\mathcal{A}$$, which cannot later be revoked. Again, note that each vertex in $$\mathcal{A}$$ can be matched $$Q$$ times.

## What I thought

Splitting approach: Split each vertex in $$\mathcal{A}$$ into $$Q$$ vertices such that:

• The weights from a vertex in $$\mathcal{D}$$ is duplicated for each of the $$Q$$ vertices.
• While matching, any one of the $$Q$$ vertices with same weights is chosen arbitrarily.

Thus, it turns into a one-to-one matching problem.

From this paper, the online version of such a problem can be solved with an algorithm with a competitive ratio of $$2n-1$$ where $$n$$ is the number of vertices. However, this splitting approach leads to an increase in the size of $$n$$ i.e. $$n = |\mathcal{A}| Q + |\mathcal{D}|$$, which leads to poor performance if quota $$Q$$ is large.

Is there a better alternative approach? I will be grateful anyone can point me towards any relevant resources.