"大数据-算法-同类平行机在线半在线排序参数界的若干研究"
本文研究了同类平行机上的在线、半在线排序问题,并对相关算法进行了设计和分析。首先,我们介绍了排序问题的基本概念,并给出了相关符号和定义。然后,我们研究了三台同类机上的在线排序问题Q3/online/Cmax,并设计了一个在线算法CS,其竞争比为2。接下来,我们研究了两台同类机上的半在线排序问题,并设计了两个半在线算法CSM和HSMP。最后,我们研究了在三台特殊的同类机上,预先知道工件最大长度这一部分信息下的半在线机器覆盖问题,并设计了一个半在线算法,其竞争比为 max{2,t}。
在在线排序问题中,我们证明了CS算法是最好的在线算法,其竞争比为2。当机器速度比向量(s,t) e G1UG2时,CS算法是最好的在线算法,而当(s,t) e G2时,算法的竞争比为t + 1。我们还证明了对于任意的S算法,其竞争比不超过t + 1,并且在常数竞争比的意义下,CS算法是最好的在线算法。
在半在线排序问题中,我们设计了两个半在线算法CSM和HSMP。其中,CSM算法的竞争比为max{s,t},而HSMP算法的竞争比为max{s,t + 1}。我们还证明了当S e (x/2,1 + √5)时,HSMP算法比CS算法的性能要好。此外,我们还证明了当S > 5.715时,该半在线问题的下界等于“纯”在线算法CS的竞争比,这也就意味着此时预先知道工件最大长度这一部分信息对改进算法的性能没有用处。
在半在线机器覆盖问题中,我们设计了一个半在线算法,其竞争比为marr{2,t}。我们还证明了该半在线问题的下界是尬处{2,t}。因此,当S < 6时,该算法是最好的半在线算法;而且,在常数竞争比的意义下,该算法是最好的半在线算法,其竞争比为3。
本文研究了同类平行机上的在线、半在线排序问题,并设计了多个算法以解决这些问题。这些算法的竞争比均达到最优,并且在实际应用中具有重要的参考价值。