Online rectangle filling

We 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 ( n 2 ) -time optimal algorithm for the offline version of the problem, where n is the size of the input, which improves the O ( n 3 ) -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.

Authors

• Haitao Wang School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China
• Amitabh Chaudhary
• Danny Z. Chen University of Notre Dame

Keywords

• Online algorithm
• Competitive analysis
• Competitive ratio
• Lower bound
• Resource allocation
• Channel-aware scheduling
• Wireless network