Maximum Matchings via Glauber Dynamics

Show simple item record Jindal, Anant Kochar, Gazal Pal, Manjish 2014-03-24T18:36:54Z 2014-03-24T18:36:54Z 2011-07
dc.identifier.citation Jindal, Anant; Kochar, Gazal and Pal, Manjish, “Maximum matchings via glauber dynamics”, arXiv, Cornell University Library,DOI:, Jul. 2011. en_US
dc.identifier.uri arXiv:1107.2482
dc.description.abstract In this paper we study the classic problem of computing a maximum cardinality matching in general graphs G=(V,E). The best known algorithm for this problem till date runs in O(mn√) time due to Micali and Vazirani \cite{MV80}. Even for general bipartite graphs this is the best known running time (the algorithm of Karp and Hopcroft \cite{HK73} also achieves this bound). For regular bipartite graphs one can achieve an O(m) time algorithm which, following a series of papers, has been recently improved to O(nlogn) by Goel, Kapralov and Khanna (STOC 2010) \cite{GKK10}. In this paper we present a randomized algorithm based on the Markov Chain Monte Carlo paradigm which runs in O(mlog2n) time, thereby obtaining a significant improvement over \cite{MV80}. We use a Markov chain similar to the \emph{hard-core model} for Glauber Dynamics with \emph{fugacity} parameter λ, which is used to sample independent sets in a graph from the Gibbs Distribution \cite{V99}, to design a faster algorithm for finding maximum matchings in general graphs. Our result crucially relies on the fact that the mixing time of our Markov Chain is independent of λ, a significant deviation from the recent series of works \cite{GGSVY11,MWW09, RSVVY10, S10, W06} which achieve computational transition (for estimating the partition function) on a threshold value of λ. As a result we are able to design a randomized algorithm which runs in O(mlog2n) time that provides a major improvement over the running time of the algorithm due to Micali and Vazirani. Using the conductance bound, we also prove that mixing takes Ω(mk) time where k is the size of the maximum matching. en_US
dc.description.statementofresponsibility by Anant Jindal, Gazal Kochar and Manjish Pal
dc.language.iso en en_US
dc.publisher arXiv, Cornell University Library en_US
dc.subject Algorithms en_US
dc.subject Data Structures en_US
dc.title Maximum Matchings via Glauber Dynamics en_US
dc.type Preprint

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account