Search Results

Documents authored by Olesker-Taylor, Sam

Document
DOI: 10.4230/LIPIcs.AofA.2024.20
Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm

Authors: Sam Olesker-Taylor

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
In the hardcore model, certain vertices in a graph are active: the active vertices must form an independent set. We extend this to a multicoloured version: instead of simply being active or not, the active vertices are assigned a colour; active vertices of the same colour must not be adjacent. This models a scenario in which two neighbouring resources may interfere when active - eg, short-range radio communication. However, there are multiple channels (colours) available; they only interfere if both use the same channel. Other applications include routing in fibreoptic networks. We analyse Glauber dynamics. Vertices update their status at random times, at which a uniform colour is proposed: the vertex is assigned that colour if it is available; otherwise, it is set inactive. We find conditions for fast mixing of these dynamics. We also use them to model a queueing system: vertices only serve customers in their queue whilst active. The mixing estimates are applied to establish positive recurrence of the queue lengths, and bound their expectation in equilibrium.
Cite as

Sam Olesker-Taylor. Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{oleskertaylor:LIPIcs.AofA.2024.20,
  author =	{Olesker-Taylor, Sam},
  title =	{{Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.20},
  URN =		{urn:nbn:de:0030-drops-204558},
  doi =		{10.4230/LIPIcs.AofA.2024.20},
  annote =	{Keywords: mixing time, queueing theory, hardcore model, proper colourings, independent set, data transmission, randomised algorithms, routing, scheduling, multihop wireless networks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.109
Geometric Bounds on the Fastest Mixing Markov Chain

Authors: Sam Olesker-Taylor and Luca Zanetti

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In the Fastest Mixing Markov Chain problem, we are given a graph G = (V, E) and desire the discrete-time Markov chain with smallest mixing time τ subject to having equilibrium distribution uniform on V and non-zero transition probabilities only across edges of the graph [Boyd et al., 2004]. It is well-known that the mixing time τ_RW of the lazy random walk on G is characterised by the edge conductance Φ of G via Cheeger’s inequality: Φ^{-1} ≲ τ_RW ≲ Φ^{-2} log|V|. Edge conductance, however, fails to characterise the fastest mixing time τ^⋆ of G. Take, for example, a graph consisting of two n-vertex cliques connected by a perfect matching: its edge conductance is Θ(1/n), while τ^⋆ can be shown to be O(log n). We show, instead, that is possible to characterise the fastest mixing time τ^⋆ via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance Ψ of G: Ψ^{-1} ≲ τ^* ≲ Ψ^{-2}(log|V|)^2. We prove this result by first relating vertex conductance to a new expansion measure, which we call matching conductance. We then relate matching conductance to a variational characterisation of τ^⋆ (or, more precisely, of the fastest relaxation time) due to Roch [Roch, 2005]. This is done by interpreting Roch’s characterisation as a particular instance of fractional vertex cover, which is dual to fractional matching. We believe matching conductance to be of independent interest and might have further applications in studying connectivity properties of graphs. This characterisation forbids fast mixing for graphs with small vertex conductance. To bypass this fundamental barrier, we consider Markov chains on G with equilibrium distribution which need not be uniform, but rather only ε-close to uniform in total variation. We call such chains almost mixing. We show that it is always possible to construct an almost mixing chain with mixing time τ ≲ ε^{-1} (diam G)² log |V|. Our proof is based on carefully constructing a reweighted spanning tree of G with good expansion properties and superimposing it over a simple "base" chain. In summary, our work together with known results shows that three fundamental geometric quantities characterise the mixing time on a graph according to three different notions of mixing: edge conductance characterises the mixing time of the lazy random walk, vertex conductance the fastest mixing time, while the diameter characterises the almost mixing time. Finally, we also discuss analogous questions for continuous-time and time-inhomogeneous chains.
Cite as

Sam Olesker-Taylor and Luca Zanetti. Geometric Bounds on the Fastest Mixing Markov Chain. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, p. 109:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oleskertaylor_et_al:LIPIcs.ITCS.2022.109,
  author =	{Olesker-Taylor, Sam and Zanetti, Luca},
  title =	{{Geometric Bounds on the Fastest Mixing Markov Chain}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{109:1--109:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.109},
  URN =		{urn:nbn:de:0030-drops-157051},
  doi =		{10.4230/LIPIcs.ITCS.2022.109},
  annote =	{Keywords: mixing time, random walks, conductance, fastest mixing Markov chain}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact