2019/05/26 by Tung-Wei Kuo, Kuo, Tung-Wei · 1 citation
Computer Science · Engineering · Medicine · #Age of Information Optimization #Congenital Heart Disease Studies #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #IoT Networks and Protocols
paper · pdf · doi:10.48550/arxiv.1905.10809
openalex publication_date 2019/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a transmission scheduling problem in which multiple systems receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall age of information. We call this problem the Min-Age problem. This problem is first studied by He et al. [IEEE Trans. Inform. Theory, 2018], who identified several special cases where the problem can be solved optimally in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r ≥ 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-Age problem. Second, we give a randomized 2.733-approximation algorithm and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-Age problem is NP-hard.