论文标题
有效地采样多个边
Sampling Multiple Edges Efficiently
论文作者
论文摘要
我们提出了一种额定时间算法，该算法允许以\ emph {amortized-sefficited}的方式从分布$ε$ -Close到均匀分布的分布中采样多个边缘。我们考虑邻接列表查询模型，其中通过学位和邻居查询提供了对图$ G $的访问。 伊甸园和罗森鲍姆（SOSA 18）提出了采样该模型中单个边缘的问题。让$ n $和$ m $分别表示$ g $的顶点和边缘的数量。 Eden和Rosenbaum提供了$θ^*（n/\ sqrt m）$的上限和下限，用于在一般图中采样单个边缘（其中$ o^*（\ cdot）$抑制$ \ textrm {poly}（poly}（poly}（poly}（1/ε）$）和$ \ \ \ \\ textrm {poly n log n）$ {\ log nog n）$依赖项。我们询问当需要多个样本时，是否可以避免查询复杂度的下限。也就是说，如果我们允许进行预处理阶段，我们可以得到改进的摊销每样本成本吗？我们以肯定的方式回答。 我们提出了一种算法，如果人们知道所需的样品$ q $的数量，则具有$ q $ sublinear的总成本，即$ o^*（\ sqrt q \ cdot（n/\ sqrt m）$，严格可比$ o^*（q \ cdot $ q）（n//\ ss q）$ prepant（q） Eden和Rosenbaum算法。 在这项工作的初步版本之后，tětek和Thorup（Arxiv，Preprint）证明了该界限本质上是最佳的。
We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise $ε$-close to the uniform distribution, in an \emph{amortized-efficient} fashion. We consider the adjacency list query model, where access to a graph $G$ is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let $n$ and $m$ denote the number of vertices and edges of $G$, respectively. Eden and Rosenbaum provided upper and lower bounds of $Θ^*(n/\sqrt m)$ for sampling a single edge in general graphs (where $O^*(\cdot)$ suppresses $\textrm{poly}(1/ε)$ and $\textrm{poly}(\log n)$ dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples $q$ in advance, has an overall cost that is sublinear in $q$, namely, $O^*(\sqrt q \cdot(n/\sqrt m))$, which is strictly preferable to $O^*(q\cdot (n/\sqrt m))$ cost resulting from $q$ invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tětek and Thorup (arXiv, preprint) proved that this bound is essentially optimal.
