无线网络中的在线信道分配问题

摘要

研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k+2)*/(k+1);还给出了一个竞争比为2的1-look-ahead算法.