在线问题的新模型与新方法

在线算法是组合优化和理论计算机科学领域的一个重要课题。在线算法的研究趋势在于新模型和新方法。一方面，遗留的各种在线问题需要新的思想和方法去解决；另一方面，大量新颖有意义的模型被提出。本项目的选题正在这两方面。拟研究的困难问题包括在线批处理时间表问题；在线并行任务时间表问题；实时在线时间表问题；3-Server问题。挖掘新方法，新技巧，改善原有方法，并利用其解决这些重要的在线问题，争取有突破性成果。本项目提出松弛在线模型的概念，统一和完善已有的部分信息下的在线算法体系。研究松弛程度对算法效果的本质影响，对若干传统意义下不存在有界算法的在线问题进行松弛，极大改进在线算法的竞争比。