  This paper deals with a complete bipartite matching problem with the
objective of finding an optimal matching that maximizes a certain generic
predefined utility function on the set of all matchings. After proving the
NP-hardness of the problem using reduction from the 3-SAT problem, we propose a
randomized algorithm based on Markov Chain Monte Carlo (MCMC) technique for
solving this. We sample from Gibb's distribution and construct a reversible
positive recurrent discrete time Markov chain (DTMC) that has the steady state
distribution same as the Gibb's distribution. In one of our key contributions,
we show that the constructed chain is `rapid mixing', i.e., the convergence
time to reach within a specified distance to the desired distribution is
polynomial in the problem size. The rapid mixing property is established by
obtaining a lower bound on the conductance of the DTMC graph and this result is
of independent interest.
