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.

| cite | improve this question | | | | |

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.