# Optimal Control for Generalized Network-Flow Problems

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2016.

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

- [Biased Backpressure Routing Using Link Features and Graph Neural Networks](https://mlsanity.com/paper/2407.09753/) (2024)
- [A Flexible Multi-Agent Deep Reinforcement Learning Framework for Dynamic Routing and Scheduling of Latency-Critical Services](https://mlsanity.com/paper/2510.11535/) (2025)
- [A Constrained RL Approach for Cost-Efficient Delivery of Latency-Sensitive Applications](https://mlsanity.com/paper/2603.04353/) (2026)
- [From Prior-Guided Heuristics to Deployable Agents: Accelerating Demonstration-Driven Reinforcement Learning for Deadline-Constrained Network Control](https://mlsanity.com/paper/2609.03590/) (2026)

## Abstract (arXiv)

We consider the problem of throughput-optimal packet dissemination, in the presence of an arbitrary mix of unicast, broadcast, multicast and anycast traffic, in a general wireless network. We propose an online dynamic policy, called Universal Max-Weight (UMW), which solves the above problem efficiently. To the best of our knowledge, UMW is the first throughput-optimal algorithm of such versatility in the context of generalized network flow problems. Conceptually, the UMW policy is derived by relaxing the precedence constraints associated with multi-hop routing, and then solving a min-cost routing and max-weight scheduling problem on a virtual network of queues. When specialized to the unicast setting, the UMW policy yields a throughput-optimal cycle-free routing and link scheduling policy. This is in contrast to the well-known throughput-optimal Back- Pressure (BP) policy which allows for packet cycling, resulting in excessive latency. Extensive simulation results show that the proposed UMW policy incurs a substantially smaller delay as compared to the BP policy. The proof of throughput-optimality of the UMW policy combines ideas from stochastic Lyapunov theory with a sample path argument from adversarial queueing theory and may be of independent theoretical interest.