Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2006 Copyright 2006 Universität Bonn, Institut für Informatik, Abt. V


Stopping Times, Metrics and Approximate Counting
Magnus Bordewich, Martin Dyer and Marek Karpinski
[Download PostScript] [Download PDF]

In this paper we examine the importance of the choice of metric inpath coupling, and its relationship to stopping timeanalysis. We give strong evidence that stopping time analysis is nomore powerful than standard path coupling. In particular, we prove astronger theorem for path coupling with stopping times, using ametric which allows us to analyse a one-step path coupling. Thisapproach provides insight for the design of better metrics forspecific problems. We give illustrative applications to hypergraphindependent sets and SAT instances, hypergraph colourings andcolourings of bipartite graphs, obtaining improved results for allthese problems.

* To appear in Proc. 33rd ICALP (2006).
Last Change: 11/05/14 at 10:36:41
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope