单机等长区间的在线排序问题研究

• 作者: 万龙 李文杰
• 来源期刊: 河南理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 在线排序 在线算法 等长区间 竞争比
• 年，卷（期）: 2016,（5）
• 所属期刊栏目: 基础学科
• 页码范围: 745-748
• 页数: 4页
• 分类号: TP18
• 字数: 3109字
• 语种: 中文
• DOI: 10.16186/j.cnki.1673-9787.2016.05.025

摘要

在单机区间排序环境中定义了一种新的半在线排序模型:区间是随着时间依次到达的,区间的一切信息,如到达时间、区间长度、权重等在区间的到达时刻才可获知;已知区间实例集中区间的最大权重与最小权重之比为Δ;目标是确定一个工件允许被终端抢先的排序最大化接收区间的总权重.用对手法给出了该问题的一个下界为2,接着用组合分析法设计了该问题的一个在线算法H,并用最小反例法证明其竞争比分别为(1+(4Δ+1)1/2)/2(1≤Δ≤12时)和4(Δ＞12时).表明当Δ=2时,算法H是一个最好可能的在线算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	万龙	江西财经大学信息管理学院	12	22	2.0	4.0
2	李文杰	洛阳师范学院数学科学学院	4	1	1.0	1.0