# Minimum Age TDMA Scheduling

arXiv: https://arxiv.org/abs/1905.10809 · HTML: https://mlsanity.com/paper/1905.10809/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2019.

## Built on by (most cited first, 1 of 1)

- [GCN-Driven Reinforcement Learning for Probabilistic Real-Time Guarantees in Industrial URLLC](https://mlsanity.com/paper/2506.15011/) (2025)

## Abstract (arXiv)

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 textitet 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.