2017/10/27 by Shana Moothedath, Moothedath, Shana, Prasanna Chaporkar +3 · 1 citation
Computer Science · Mathematics · #Applied mathematics #Bayesian Modeling and Causal Inference #Bipartite graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #Graph #Markov Chains and Monte Carlo Methods #Markov chain #Markov chain Monte Carlo #Markov chain mixing time #Markov model #Markov property #Matching (statistics) #Mathematical optimization #Mathematics #Mixing (physics) #Monte Carlo method #Statistics #cs.DM
paper · pdf · doi:10.48550/arxiv.1710.10037
published in arXiv (Cornell University) (Cornell University)
arxiv created 2017/10/27 · openalex publication_date 2017/10/27 · arxiv updated 2017/10/30 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
This paper deals with a complete bipartite matching problem with the\nobjective of finding an optimal matching that maximizes a certain generic\npredefined utility function on the set of all matchings. After proving the\nNP-hardness of the problem using reduction from the 3-SAT problem, we propose a\nrandomized algorithm based on Markov Chain Monte Carlo (MCMC) technique for\nsolving this. We sample from Gibb's distribution and construct a reversible\npositive recurrent discrete time Markov chain (DTMC) that has the steady state\ndistribution same as the Gibb's distribution. In one of our key contributions,\nwe show that the constructed chain is `rapid mixing', i.e., the convergence\ntime to reach within a specified distance to the desired distribution is\npolynomial in the problem size. The rapid mixing property is established by\nobtaining a lower bound on the conductance of the DTMC graph and this result is\nof independent interest.\n