Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MARKOV CHAIN MONTE CARLO:
Reports tagged with Markov Chain Monte Carlo:
TR00-079 | 12th September 2000
Mark Jerrum, Eric Vigoda

#### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

We present a fully-polynomial randomized approximation scheme
for computing the permanent of an arbitrary matrix
with non-negative entries.

more >>>

TR04-009 | 22nd January 2004
Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

#### Randomly coloring constant degree graphs

We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>

TR05-151 | 7th December 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

#### Metric Construction, Stopping Times and Path Coupling.

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>

TR11-099 | 11th July 2011
Anant Jindal, Gazal Kochar, Manjish Pal

#### Maximum Matchings via Glauber Dynamics

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani ... more >>>