
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 2005  Copyright 2005 Universität Bonn, Institut für Informatik, Abt. V  
89100 22.11.2005 
Metric Construction, Stopping Times and Path Coupling
Magnus Bordewich, Martin Dyer and Marek Karpinski [Download PostScript] [Download PDF]
In this paper we examine the importance of the choice of metric in path coupling,and the relationship of this to stopping time analysis. We give strongevidence that stopping time analysis is no more powerful than standard pathcoupling. In particular, we prove a stronger theorem for path coupling withstopping times, using a metric which allows us to restrict analysis to standardonestep path coupling. This approach provides insight for the design ofnonstandard metrics giving improvements in the analysis of specific problems. 

Last Change:
11/05/14 at 10:31:52
English 
Universität Bonn > Institut für Informatik > Abteilung V 