Fundamentals of Computation Theory

DOI10.1007/11537311zbMATH Open1123.68142arXivmath/0511202OpenAlexW2491671784MaRDI QIDQ5492913FDOQ5492913

Marek Karpinski, Magnus Bordewich, Martin Dyer

Publication date: 20 October 2006

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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 with stopping times, using a metric which allows us to restrict analysis to standard one-step path coupling. This approach provides insight for the design of non-standard metrics giving improvements in the analysis of specific problems. We give illustrative applications to hypergraph independent sets and SAT instances, hypergraph colourings and colourings of bipartite graphs.

Full work available at URL: https://arxiv.org/abs/math/0511202

Recommendations

• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Stopping Times, Metrics and Approximate Counting
• Rapid mixing of hypergraph independent sets
• Variable length path coupling
• Coupling with the stationary distribution and improved sampling for colorings and independent sets

zbMATH Keywords

Markov chainsstopping timeshypergraphmixing timeGlauber dynamicspath couplinghardness of counting

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Hypergraphs (05C65)

Cited In (1)

• Path coupling without contraction

This page was built for publication: Fundamentals of Computation Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5492913)