2
$\begingroup$

I stumbled on the Hungarian algorithm during my personal research when I was assigned interesting problem as homework:

Given a list of objects $L$ and a pairing function $\delta : L \times L \rightarrow \left[0, 1\right]$, pair each object $\alpha$ in $L$ with exactly one $\beta$ in $L$ such that:

  • $\sum_{i = 1}^n \delta(\alpha_n, \beta_n)$ is maximal
  • $(\alpha, \beta) \iff (\beta, \alpha)$
  • $(\alpha, \beta) \implies \alpha \neq \beta$

Now, since we just started programming as a class, our TA wants us to use a heuristic approach to solve the problem - e.g. swap assignments until you reach a local maximum etc.

I thought of using the Hungarian algorithm to guarantee an optimal matching in (relatively) feasible time. For this, I constructed a graph with all $\alpha$ having nodes to all $\beta$ and initializing the edge of two same elements to $\infty$.

However, as it turns out, the implementation I wrote disregards the symmetric aspect of this matrix - in other words my algorithm does not guarantee that $\alpha$ is also it's the partner of the partner of $\alpha$.

I suspect that reason for this is that this is not a bipartite graph anymore. Even though there is a difference between an $\alpha$ on the left and a $\beta$ on the right, it's not a "real" bipartite graph. Is this correct?

According to the Math stack exchange I should use the more general blossom algorithm in this case, but somehow I have a feeling that I could make better use of the properties of my matrix. Is there a better algorithm for this case?

$\endgroup$
  • 1
    $\begingroup$ Not an answer. The name of the problem is weighted perfect matching in complete graphs (with no self-loops). $\endgroup$ – aelguindy Nov 7 '16 at 20:20
1
$\begingroup$

Your problem is exactly the same as maximum weight perfect matching, solved by the blossom algorithm. Although $\delta$ is not given as symmetric, you can reduce your problem to the symmetric case by replacing $\delta$ with $$ \delta'(\alpha,\beta) = \max(\delta(\alpha,\beta),\delta(\beta,\alpha)). $$ I'll let you figure out how to translate a solution which is optimal with respect to $\delta'$ to one which is optimal with respect to $\delta$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.