摘要
研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k+2)/(k+1);还给出了一个竞争比为2的1-look-ahead算法.
We consider an online maximization problem in wireless channel scheduling. We give an O(n2) algorithm for the offline version. For the online version we provide a natural lower bound of (k+2)?(k+1) in the general k-look-ahead setting, and a 2-competitive online algorithm in the 1-look-ahead setting.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第z1期31-34,共4页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60573025)
关键词
在线算法
竞争比
online algorithm
competitive analysis
