论文标题
广播充血集团中的拉普拉斯范式
The Laplacian Paradigm in the Broadcast Congested Clique
论文作者
论文摘要
在本文中，我们将Laplacian范式的主要工具带到了广播的拥塞集团。我们引入了一种算法，以在多个弹药数量中计算光谱稀疏器，这直接导致有效的laplacian求解器。基于此原始性，我们考虑了Lee和Sidford的线性程序求解器（FOCS 2014）。我们展示了如何求解某些线性程序到加性错误$ε$，并在$ n $ vertex广播拥堵的集体网络上使用$ \ tilde o（\ sqrt {n} \ log（1/ε））$回合。使用此信息，我们展示了如何在$ \ tilde o（\ sqrt {n}）$ rounds中找到最低成本流问题的精确解决方案。
In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver. Based on this primitive, we consider the linear program solver of Lee and Sidford (FOCS 2014). We show how to solve certain linear programs up to additive error $ε$ with $n$ constraints on an $n$-vertex Broadcast Congested Clique network in $\tilde O(\sqrt{n}\log(1/ε))$ rounds. Using this, we show how to find an exact solution to the minimum cost flow problem in $\tilde O(\sqrt{n})$ rounds.
