2017-Maintaining Densest Subsets Efficiently in Evolving Hypergraphs

研究问题：超图下的密度子图提取及其动态维护

1） 静态超图的准确算法：

①类比于普通图，用网络流建图即可

②用线性规划求解

2）静态超图的近似算法：

①r-近似算法 直接剥离权重最小的点即可

②$r(1+\epsilon)$ 近似算法 剥离的是一个集合，为后续任务服务

3） 动态超图只能近似维护

① 只维护插入

② 插入和删除一起维护

这里只维护插入会比删除要简单的多，因此会分开讨论

下面是ppt讲解部分：

最后是补充一下原论文：