New Algorithms for Online Rectangle Filling with k-Lookahead

摘要：

We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present improved deterministic and first known randomized results for algorithms that are allowed a k-lookahead for k≥2.Our main result is a deterministic min1.848,1 + 2/(k-1)competitive online algorithm. The previous best-known solution for this problem has a competitive ratio of 2 for any k≥2.We also present a randomized online algorithm with a competitive ratio of 1 + 1/(k + 1). Our final result is a closely matching lower bound of 1 + 1/(√k + 2 + √k + 1)2 > 1 + l/(4(k + 2)) on the competitive ratio of any randomized online algorithm against an oblivious adversary.

作者: Haitao Wang Amitabh Chaudhary Danny Z. Chen

作者单位: Department of Computer Science and Engineering University of Notre Dame, Notre Dame, IN 46556, USA

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 385-394

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）