哈尔滨工业大学（HIT）《算法设计与分析》课程报告

哈尔滨工业大学《算法设计与分析》课程报告 本报告对哈尔滨工业大学《算法设计与分析》课程的报告进行了总结。该报告的主要内容是 Faster Cut Sparsification of Weighted Graphs，讨论了图稀疏化算法的改进。该算法可以在多项式时间内计算出加权图的稀疏化结果。 算法描述： 我们的稀疏化算法的高层设置与 Fung 等人[FHHP19]的非加权图的算法相似。我们的主要贡献在于通过使用最大生成森林（MSF）指数而非 Nagamochi-Ibaraki（NI）指数，展示了如何将该技术推广到加权图。我们证明了通过收紧分析，大小和时间界限以高概率成立，而不仅仅是在期望值中。 算法的主要步骤包括： 1. 计算一个�-部分 MSF 包装的算法，时间为� � ⋅ min � � log � , log �。 2. 计算多项式加权图的部分 MSF 包装。 3. 对于无界权值，可以计算一个充分的估计，时间也是� � ⋅ min � � log � ,log �。 我们的算法可以 guarantee 在多项式时间内计算出加权图的稀疏化结果，且 sizes 和时间界限以高概率成立。 算法分析： 我们的算法的主要贡献在于使用最大生成森林（MSF）指数，而非 Nagamochi-Ibaraki（NI）指数。这使得我们可以将非加权图的稀疏化算法推广到加权图中。我们证明了 MSF 指数是加权图中 NI 指数的自然类似物。 我们还证明了我们的算法可以 guarantee 在多项式时间内计算出加权图的稀疏化结果。我们的算法包括两个主要阶段。在第一阶段，我们计算集合�0, �1, …, �� ⊆ �，其中的边满足对分离其端点的任何切口的权重的一些下限。在第二阶段，我们以相应的概率从每个集合��中抽取边。 结论： 我们的算法可以 guarantee 在多项式时间内计算出加权图的稀疏化结果，且 sizes 和时间界限以高概率成立。我们的算法可以应用于许多实际问题中，例如社交网络、交通网络等。