Online rectangle filling

AbstractWe study an online geometric problem arising in channel-aware scheduling of wireless networks, which we call the online rectangle filling. We present an online algorithm (with one-lookahead) for this problem with a competitive ratio of 1.848, improving the previously best-known 8/3-competitive algorithm in Arora et al. (2006) [4]. We also prove a lower bound of 1.6358 on the competitive ratio of the problem, improving the previous 1.6 lower bound in [4]. In addition, we give an O(n2)-time optimal algorithm for the offline version of the problem, where n is the size of the input, which improves the O(n3)-time solution in Arora and Choi (2006) [3], Arora et al. (2006) [5]. Our techniques are based on interesting techniques and new observations of the combinatorial structures in the problem