Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

Revisions: 1 , Comments: 1

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

ISSN 1433-8092 | Imprint