All reports by Author Eric Vigoda:

__
TR04-009
| 22nd January 2004
__

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda#### Randomly coloring constant degree graphs

__
TR00-079
| 12th September 2000
__

Mark Jerrum, Eric Vigoda#### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

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 Δ. 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> ≥ <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>

Mark Jerrum, Eric Vigoda

We present a fully-polynomial randomized approximation scheme

for computing the permanent of an arbitrary matrix

with non-negative entries.