Competitive Analyses of Online Minimum Age of Information Transmission Scheduling
Tung-Wei Kuo · IEEE INFOCOM 2022 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · 2022
We consider a system that consists of one sender and n receivers, and the goal is to schedule message transmissions to minimize the total age of information of all receivers. Unlike most prior work, we assume that receivers arrive over time, and there are only a finite number of messages for each receiver. These natural assumptions, however, make it challenging to design and analyze scheduling algorithms. In this paper, we give the competitive ratios of some common scheduling algorithms, and prove that for every scheduling algorithm, the competitive ratio is $\Omega\left(n^{\frac{1}{5}}\right)$.