传感器网络中最小 k-连通 m-控制集问题的近似算法?

在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小 k-连通 m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小 k-连通 m-控制集问题,给出了一个构造最小 k-连通 m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性.     

社交网络中的虚假信息经加边修正最大化问题

在线社交网络如微信等的普及,使人们更加关注信息传播的问题。虚假信息在社交网络中进行传播可能会造成很严重的后果,比如经济损失或者公众恐慌等。因此,需要采取相关的措施来控制虚假信息的传播。传统的虚假信息控制方法主要通过向网络中的部分节点传播真实信息,让真实信息和虚假信息进行竞争来减小虚假信息的影响。文中将传播真实信息和加边的方式相结合,提出了一个虚假信息修正最大化问题。该问题是NP-难的,其目标函数值的计算是#P-难的。由于目标函数既不是次模的也不是超模的,因此采用三明治近似策略来求解该问题。为此,构造目标函数的次模的上界和下界函数,利用反向影响采样技术在基数约束下求解上界和下界函数,最终得到原问题的一个数据相关的近似解。通过在3个真实网络的数据集上进行仿真实验,验证了所提算法的有效性。     

Lp范数下2台机器并行工件在线排序问题研究

本文研究一类并行工件平行机在线排序问题。给定2台平行机和一组按列表到达的并行工件,对每一到达的工件进行机器指派和确定开工时间,使得机器完工时间的lp范数最小。本文首先分析了LS算法的竞争比,其值为2;其次证明了任何在线算法的竞争比不小于4/3。