We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present deterministic and randomized results for algorithms that are allowed a k‐lookahead for k≥2. Our main result is a deterministic min {1.848,1+2/(k-1)}‐competitive online algorithm. This is the first algorithm for this problem with a competitive ratio approaching 1 as k approaches +∞. 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 (also proved in this paper) of
on the competitive ratio of any randomized online algorithm against an oblivious adversary. These are the first known results for randomized algorithms for this problem.
