1 Search Results for "Hu, Nathan"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.83
Sampling Arborescences in Parallel

Authors: Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem has long been known to be polynomial-time solvable; the exact number of arborescences can be computed by a determinant [Tutte, 1948], and sampling can be reduced to counting [Jerrum et al., 1986; Jerrum and Sinclair, 1996]. However, the classic reduction from sampling to counting seems to be inherently sequential. This raises the question of designing efficient parallel algorithms for sampling. We show that sampling arborescences can be done in RNC. For several well-studied combinatorial structures, counting can be reduced to the computation of a determinant, which is known to be in NC [Csanky, 1975]. These include arborescences, planar graph perfect matchings, Eulerian tours in digraphs, and determinantal point processes. However, not much is known about efficient parallel sampling of these structures. Our work is a step towards resolving this mystery.
Cite as

Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. Sampling Arborescences in Parallel. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 83:1-83:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anari_et_al:LIPIcs.ITCS.2021.83,
  author =	{Anari, Nima and Hu, Nathan and Saberi, Amin and Schild, Aaron},
  title =	{{Sampling Arborescences in Parallel}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{83:1--83:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.83},
  URN =		{urn:nbn:de:0030-drops-136225},
  doi =		{10.4230/LIPIcs.ITCS.2021.83},
  annote =	{Keywords: parallel algorithms, arborescences, spanning trees, random sampling}
}
  • Refine by Author
  • 1 Anari, Nima
  • 1 Hu, Nathan
  • 1 Saberi, Amin
  • 1 Schild, Aaron

  • Refine by Classification
  • 1 Theory of computation → Generating random combinatorial structures
  • 1 Theory of computation → Parallel algorithms
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 arborescences
  • 1 parallel algorithms
  • 1 random sampling
  • 1 spanning trees

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact