| 摘要 | 第1-5页 |
| Abstract | 第5-8页 |
| 第1章 引言 | 第8-9页 |
| 第2章 历史注记及相关工作 | 第9-12页 |
| 第3章 形式化定义 | 第12-19页 |
| ·预备知识 | 第12-14页 |
| ·在线算法与竞争比 | 第12-13页 |
| ·随机在线算法的竞争比 | 第13-14页 |
| ·关于Look-ahead概念的注记 | 第14-15页 |
| ·在线信道分配问题(Channel Scheduling Problem) | 第15-16页 |
| ·接金币问题(Windfall Problem) | 第16-17页 |
| ·收益任务系统问题(Benefit Task System Problem) | 第17-19页 |
| 第4章 在线信道分配问题 | 第19-33页 |
| ·离线问题 | 第19页 |
| ·无前瞻能力的在线问题(1-look-ahead) | 第19-20页 |
| ·带前瞻能力的在线问题(K>1) | 第20-22页 |
| ·一个一般下界 | 第20-21页 |
| ·Intermittent Reset Algorithm | 第21-22页 |
| ·K=2的情况 | 第22-29页 |
| ·一个2-competitive的在线算法 | 第23-26页 |
| ·DFA Algorithm | 第26-27页 |
| ·一个13/8的竞争比下界 | 第27-29页 |
| ·随机在线算法 | 第29-33页 |
| ·无前瞻能力的情形(1-look-ahead) | 第29-30页 |
| ·对任意K的随机算法 | 第30页 |
| ·下界问题 | 第30-33页 |
| 第5章 接金币问题 | 第33-45页 |
| ·一个1+(d/k')下界 | 第33-35页 |
| ·离线算法 | 第35-36页 |
| ·在线算法 | 第36-45页 |
| ·一个简单的(d+1)-competitive算法 | 第36页 |
| ·GBP Algorithm | 第36-37页 |
| ·对d=1的算法 | 第37-39页 |
| ·对一般d的算法 | 第39-41页 |
| ·一个(1+(d~2)/k')-competitive的算法 | 第41-43页 |
| ·一个实用的算法 | 第43-45页 |
| 第6章 总结与展望 | 第45-48页 |
| ·主要结果 | 第45-46页 |
| ·问题推广 | 第46-47页 |
| ·后续工作 | 第47-48页 |
| 第7章 致谢 | 第48-49页 |
| 插图索引 | 第49-50页 |
| List of Algorithms | 第50-51页 |
| 参考文献 | 第51-54页 |
