An improved algorithm for online rectangle filling (Q418006)

This paper considers the problem of using optimally wireless channel while the capacity of the channel varies over time. The time is discretised and a slot of time corresponds to the time needed to transmit data and to synchronize the transmitter/receptor in the case where the transmitter changes the transmission rate.The capacity of the channel is supposed to be known, or estimated, by the transmitter for the next slot of time. Given this information, the transmitter faces the problem of deciding what is the optimal transmission rate, given that changing the rate of transmission `consumes' one time slot. This means that if the capacity of the next time slot increases, increasing the transmission rate will be effective two time slots later and the next one is lost for transmission. The algorithm presented in the paper improves the competitive ratio of previous algorithms. The idea that leads to this improvement is to avoid changing the rate of transmission and, in particular, to avoid that a new time slot with high capacity triggers the change of transmission rate. The algorithm also improves the lower bound of the problem as well as the randomized lower bound.