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

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

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

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

一类带多重核元集在线装箱问题

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法.该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进.通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度.实验仿真表明算法是可行有效的.

“四融合”模式下的“最优化理论与算法”课程教学改革探索

本文结合“思教、科教、创教、产教”四融合,对研究生课程“最优化理论与算法”内容体系和教学方法进行了探索,分析了课程中存在的问题和教学改革的必要性,重构了课程内容体系、提出互动探究式教学、思教融合、科教融合、加强过程考核等举措,激发学生学习热情,明确学习目标,提高课程教学质量和育人成效。

含4-圈且不含3-圈的P_4-等可覆盖图的刻画

覆盖问题是图论的主要研究内容,也是理论计算机科学中的重要内容之一,具有重要的理论意义与应用价值,在计算机图形学和运筹学中都有广阔的应用前景。在通信行业,基于覆盖问题的研究基础,可以简化通信网络的层次分布与优化。特殊的覆盖可以导出图的一些良好的性质,鉴于这类问题在实际应用中的价值,此类研究近期应用于图的结构性之上。图论中的覆盖问题有很多种,其中包括等可覆盖问题:如果一个图G的每个极小H-覆盖都是它的最小H-覆盖,则称G为H-等可覆盖的。本文仅考虑H为P4时的情形。经过讨论,本文通过对含4-圈且不含3-圈的图的特征进行刻画,给出了判定任意一个含4-圈且不含3-圈的图是否是P4-等可覆盖的充分必要条件。

基于超图的社交网络中的预算影响力最大化

影响力最大化问题是在线社交网络中的热点问题,然而社交网络的结构错综复杂,传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足,利用有向超图刻画社交用户之间的群体影响,提出一种基于有向超图的预算影响力最大化问题.该问题是在有向超图的社交网络中,在给定预算下,寻找高影响力用户作为种子节点集,使得其最终的传播范围最大化.分析了该问题是NP-hard的且目标函数是非次模函数,提出了改进的贪婪算法和交换启发式算法进行求解,并分析了改进贪婪算法的近似比.通过将所提的算法应用到三个在线社交网络数据集中进行实验,验证了算法的正确性和良好性能.结果表明,改进贪婪算法基础上的交换启发式算法具有明显的性能优势.

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

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

基于生成对抗网络去除单张图像中的雨滴

本次研究主要源自于单张图像中的雨滴去除问题。由于附着在玻璃窗或者相机镜头上的雨滴会严重降低图像的质量,因而使用生成对抗网络将带有雨滴的退化图像转换为干净的图像来解决此问题。文章的主要思想是将视觉注意力机制引入到生成网络中,提出新的残差U-Nets处理注意力图,并使用判别网络进行甄别图像的真实性,同时使用新的感知损失作为损失函数,从而使网络可以更加关注雨滴区域及其周围的环境。这样处理不但可以使恢复的图像具有更高的质量,同时也能具有更加优秀的视觉效果。文章采用峰值信噪比和结构相似性作为模型的数值评价标准,图像的细节展示作为视觉评价标准。实验表明,这种方法无论在视觉效果,还是数值结果上都具有不错的表现。

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件,每个工件包含两类任务:Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析,得到其一般情形下的竞争比当s≥(1+51/2)/2时为1+1/s,否则为1+s/(s+1)。而当每个工件Jj都满足其Map任务总长大于等于Reduce任务总长时,其竞争比当s≥(1+31/2)/2时不超过1+1/(2s),否则为不超过1+s/(2s+1)。

考虑用户意愿的符号网络净积极影响力最大化问题

影响力最大化是近年来广泛研究的社交网络的核心问题.然而之前的研究较少考虑用户的意愿以及用户之间的友好或敌对关系.因此综合考虑这些因素,针对符号网络提出了考虑用户意愿的净积极影响力最大化问题,该问题可以描述如下:利用符号网络来刻画用户具有友好(积极)和敌对(消极)关系的社交网络,每个用户对传播的信息有自己的意愿,目标是要从网络中选择k个用户,使得最终的净积极影响的用户数量最多.通过对问题的细致分析,建立了考虑用户意愿的传播模型,证明了该模型下净积极影响力最大化问题是非次模和非单调的,随后给出了基于概率驱动的结构感知的求解算法,通过在三个数据集上的实验表明,利用提出的算法找到的种子集有更好的净积极影响力.

恒速机上的MapReduce在线排序算法下界研究

本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小。对|M_j|≥|R_j|的情形,我们证明了任意在线算法的竞争比不小于1+(1/(2s+2)).

箱子是在线到达的带核元变尺寸装箱问题

本文考虑了一类箱子在线到达的带核元变尺寸装箱问题.假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物件表,目标是要将表中元素装入到达的箱子中,使得所用的箱子总长最小.我们首先证明了该问题是强NP-Hard,其次分析了经典算法NF(D)和FF(D)的性能界,指出NF(D)和FF(D)算法的性能界可以任意大.最后我们给出了相应的修改算法MNF(D)和MFF(D),证明了它们的性能界都是3,此界是紧的.

几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0<ρ<1)1的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.