World's most popular travel blog for travel bloggers.

# Assignment algorithm for symmetric matrices

, ,
Problem Detail:

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?

###### Answered By : Yuval Filmus

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$.