# Online Network Utility Maximization: Algorithm, Competitive Analysis, and Applications

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2021.

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

- [Learning Wireless Interference Patterns: Decoupled GNN for Throughput Prediction in Heterogeneous Multi-Hop p-CSMA Networks](https://mlsanity.com/paper/2510.14137/) (2025)
- [A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives](https://mlsanity.com/paper/2406.03574/) (2024)

## Abstract (arXiv)

We consider an online version of the well-studied network utility maximization problem, where users arrive one by one and an operator makes irrevocable decisions for each user without knowing the details of future arrivals. We propose a threshold-based algorithm and analyze its worst-case performance. We prove that the competitive ratio of the proposed algorithm is linearly increasing in the number of links in a network and show this competitive analysis is tight. Extensive trace-driven simulations are conducted to demonstrate the performance of our proposed algorithm. In addition, since worst-case scenarios rarely occur in practice, we devise an adaptive implementation of our algorithm to improve its average-case performance and validate its effectiveness via simulations.