# Energy-Aware Wireless Scheduling with Near Optimal Backlog and Convergence Time Tradeoffs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2014.

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

- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)

## Abstract (arXiv)

This paper considers a wireless link with randomly arriving data that is queued and served over a time-varying channel. It is known that any algorithm that comes within ε of the minimum average power required for queue stability must incur average queue size at least Omega(log(1/ε)). However, the optimal convergence time is unknown, and prior algorithms give convergence time bounds of O(1/ε2). This paper develops a scheduling algorithm that, for any ε>0, achieves the optimal O(log(1/ε)) average queue size tradeoff with an improved convergence time of O(log(1/ε)/ε). This is shown to be within a logarithmic factor of the best possible convergence time. The method uses the simple drift-plus-penalty technique with an improved convergence time analysis.