项目简介
项目名称
可中断排序相关问题研究及前沿应用
项目批准号
11001242
学科分类
A011202
数理科学部
_数学
_运筹学
_组合最优化
资助类型
数理科学
负责人
蒋义伟
依托单位
浙江理工大学
批准年份
2010
起止时间
201101-201312
批准金额
17.00万元
摘要
随着可中断排序问题的深入研究，与可中断排序密切相关的新问题也不断的涌现。本项目主要研究可中断排序的相关问题以及前沿问题的可中断算法设计，包括利用最优可中断在线算法研究不可中断排序，机器带特殊性质时机器空闲对可中断算法设计的影响，可中断算法与随机下界、随机算法的关系，可中断次数受限和带中断惩罚费用的排序问题以及可中断算法在CPU能耗管理中的应用。对离线问题，研究其计算复杂性，设计最坏情况界尽可能小的近似算法或近似方案。对（半）在线问题，用竞争比分析给出问题的下界和设计在线算法。通过本项目对可中断排序更为深入的理论研究和相关问题的算法设计与应用研究，在理论上进一步丰富和完善了排序问题的研究内容和算法设计与分析的技巧，在实际中进一步拓展排序理论的应用领域，具有一定的理论意义和应用价值。
评论区 (0)
#插入话题
