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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.