带前瞻的在线最大化问题

论文摘要

本文讨论了两个自然带前瞻的在线最大化问题,并分析了竞争比的上下界。对在线信道分配问题,我们给出了一个O（n2）的离线算法,一个（K+1）/K的竞争比下界,和一个（1+1/（（?）（K-1）/2（?）））-comopetitive的在线算法（K＞2）。对K=2的情况,我们设计了一个2-competitive的在线算法,并将下界提高到13/8。我们还给出了一个（K+1）/K-competitive的随机在线算法,并对较小的K给出了几个随机算法的下界。对接金币问题,我们对一般的d和K给出了一个1+d/k′的自然下界,并设计了在渐进意义上达到该下界的在线算法。对d=1的情形,我们给出了完全达到下界1+1/K的算法。我们还给出了一个对较小的K有更好竞争比的实用算法。本文中我们重新定义了在线算法中前瞻的概念,使其更适合于自然带前瞻的在线问题。我们还提出了一种新的在线算法的设计思路,并将其应用到这两个问题中。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 第2章 历史注记及相关工作
• 第3章 形式化定义
• 3.1 预备知识
• 3.1.1 在线算法与竞争比
• 3.1.2 随机在线算法的竞争比
• 3.2 关于Look-ahead概念的注记
• 3.3 在线信道分配问题（Channel Scheduling Problem）
• 3.4 接金币问题（Windfall Problem）
• 3.5 收益任务系统问题（Benefit Task System Problem）
• 第4章 在线信道分配问题
• 4.1 离线问题
• 4.2 无前瞻能力的在线问题（1-look-ahead）
• 1）'>4.3 带前瞻能力的在线问题（K>1）
• 4.3.1 一个一般下界
• 4.3.2 Intermittent Reset Algorithm
• 4.4 K=2的情况
• 4.4.1 一个2-competitive的在线算法
• 4.4.2 DFA Algorithm
• 4.4.3 一个13/8的竞争比下界
• 4.5 随机在线算法
• 4.5.1 无前瞻能力的情形（1-look-ahead）
• 4.5.2 对任意K的随机算法
• 4.5.3 下界问题
• 第5章 接金币问题
• 5.1 一个1+（d/k'）下界
• 5.2 离线算法
• 5.3 在线算法
• 5.3.1 一个简单的（d+1）-competitive算法
• 5.3.2 GBP Algorithm
• 5.3.3 对d=1的算法
• 5.3.4 对一般d的算法
• 2）/k'）-competitive的算法'>5.3.5 一个（1+（d²）/k'）-competitive的算法
• 5.3.6 一个实用的算法
• 第6章 总结与展望
• 6.1 主要结果
• 6.2 问题推广
• 6.3 后续工作
• 第7章 致谢
• 插图索引
• List of Algorithms
• 参考文献