通过输入扰动优化私密最小生成树的界限

本文研究了在边权差分隐私下，发布近似最小生成树的问题，填补了现有算法在计算效率与准确性之间的权衡空白。我们提出了一种新的方法，通过适当的随机扰动输入，使得任何非私密的最小生成树算法的结果能够同时满足隐私性和达到最佳的错误保证。此外，我们建立了与私密Top-k选择的联系，首次得出了最小生成树在近似差分隐私下的隐私-效用权衡下界，展示了我们的误差幅度是最佳的。