























We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an $(ε, δ)$-spectral sparsifier with multiplicative error $ε$ and additive error $δ$ that has $O(ε^{-2} n \log n \log r \log(1 + εW/δn))$ hyperedges with high probability, where $ε, δ\in (0,1)$, $n$ is the number of nodes, and $W$ is the sum of edge weights. The space complexity of our algorithm is $O(n^2)$, while previous algorithms require the space complexity of $Ω(m)$, where $m$ is the number of hyperedges. This provides an exponential improvement in the space complexity since $m$ can be exponential in $n$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。