⚡ electrical engineering

On the Optimality of Rate Balancing for Max-Min Fair Multicasting

This paper analytically derives the optimal solution to the NP-hard max-min fair multicasting problem by establishing its equivalence to rate balancing under specific conditions, leading to a proposed low-complexity algorithm that yields closed-form solutions and outperforms state-of-the-art methods.

Original authors: Sadaf Syed, Wolfgang Utschick, Michael Joham

Published 2026-02-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sadaf Syed, Wolfgang Utschick, Michael Joham

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a radio tower (the Base Station) trying to shout a single message to a group of people (the Users) scattered around a field. Some people are close and hear clearly; others are far away or blocked by obstacles and hear poorly. The goal of this paper is to figure out the best way for the tower to shout so that the person with the worst hearing still hears as clearly as possible.

In technical terms, this is called "Max-Min Fair Multicasting." The authors found that this problem is notoriously difficult to solve (mathematically "NP-hard"), meaning most existing methods are just guessing or using very slow, heavy-duty computers to get a "good enough" answer.

Here is the simple breakdown of what the authors discovered and built:

1. The Core Problem: The "Weakest Link"

Think of the radio tower as a teacher trying to teach a class. If the teacher speaks too loudly, the students in the back might not hear, but if they speak too softly, the students in the front might be bored. The "Max-Min" rule says: Don't worry about making the front-row students perfect; focus entirely on making sure the back-row student can hear.

The challenge is that the "noise" and "obstacles" for each student are different. Finding the perfect volume and direction for the teacher's voice to help the worst-off student is a massive mathematical puzzle.

2. The Old Way vs. The New Way

The Old Way (SDR/CVX): Imagine trying to solve a complex maze by testing every single path one by one with a slow, heavy robot. It eventually finds the exit, but it takes a long time and uses a lot of battery. This is how current methods work; they use powerful solvers that are accurate but slow.
The New Way (The Authors' Algorithm): The authors realized something clever. They proved that under specific conditions (when the number of students isn't too huge compared to the number of antennas the tower has), the perfect solution is simply to make everyone hear at the exact same volume.

3. The Big Discovery: "Rate Balancing"

The paper's main "Aha!" moment is the connection between optimality and balancing.

The Analogy: Imagine a group of hikers tied together by a rope. The group can only move as fast as the slowest hiker. The authors proved that if you want the group to move as fast as possible, you shouldn't try to make the slow hiker faster by pushing them; instead, you should arrange the group so that everyone is walking at the exact same speed.
The Result: They mathematically proved that if you balance the signal strength (the "hearing ability") for every user so they are all equal, you automatically get the best possible result for the worst-off user.

4. How They Did It (The "Low-Complexity" Trick)

Instead of using the slow, heavy robot (the CVX solver), the authors created a shortcut.

They used a mathematical tool called "Fractional Programming" to turn the messy, confusing problem into a clean, straight line.
Because they knew the answer involves balancing everyone, they could write down a simple formula (a "closed-form solution") to calculate the perfect settings immediately.
The Benefit: This is like switching from solving a maze by trial-and-error to just looking at the map and drawing a straight line to the exit. It is much faster and uses less computing power.

5. What the Tests Showed

The authors ran simulations to test their idea:

Scenario A (Fewer users than antennas): When the group is small, their new "Balancing" algorithm performed just as well as the slow, heavy robot methods, but much faster. In fact, it confirmed that balancing everyone's signal was indeed the perfect strategy.
Scenario B (More users than antennas): Even when the group got larger and the math got trickier, their algorithm still outperformed the other fast methods (like ADMM or SNR Inc.), often beating the heavy robot methods too.
The Visual Proof: In their graphs, you can see that the "Balancing" algorithm gives a flat line where everyone has the same Signal-to-Noise Ratio (SNR), whereas other methods leave some people with poor signals. The paper shows that this flat, balanced line actually yields the highest possible minimum signal.

Summary

The paper claims to have solved a decades-old, difficult math problem for wireless communication. They proved that making everyone's connection equal is the secret to making the worst connection as good as it can be. They built a new, lightning-fast algorithm based on this rule that works better and faster than the current state-of-the-art methods, especially in systems with many antennas (like 5G and beyond).

Technical Summary: On the Optimality of Rate Balancing for Max-Min Fair Multicasting

Problem Formulation
The paper addresses the Max-Min Fair (MMF) multicasting problem in the downlink of a multi-user Multiple-Input Single-Output (MISO) system. The objective is to design a common precoding vector that maximizes the minimum Signal-to-Noise Ratio (SNR) among all $K$ users, subject to a total transmit power constraint. The authors acknowledge that this problem is known to be NP-hard. Consequently, existing state-of-the-art solutions typically rely on suboptimal designs, such as Semidefinite Relaxation (SDR) solved via interior-point methods (e.g., CVX), Alternating Direction Method of Multipliers (ADMM), or heuristic iterative updates. While these methods can approach optimality, they often suffer from high computational complexity or fail to provide a closed-form solution. Furthermore, existing approaches generally do not investigate the structural properties of the optimal solution, particularly regarding the relationship between user rate balancing and optimality.

Methodology
The authors propose a novel approach based on Fractional Programming (FP) and Lagrangian duality to derive the optimal solution analytically.

Reformulation: The original non-convex problem is reformulated using auxiliary variables ( $\beta_k$ ) to create a block-wise convex problem (P3).
KKT Analysis: The authors analyze the Karush-Kuhn-Tucker (KKT) optimality conditions. They define sets of "active" users (those with the minimum rate) and "inactive" users (those with higher rates).
Closed-Form Solution: By deriving the dual function and minimizing it with respect to the dual variables, the authors obtain a closed-form expression for the optimal precoding vector. This involves solving a linear system of equations involving a matrix $D$ (derived from channel vectors and auxiliary variables) and a vector $d$ .
Rate Balancing Equivalence: A central theoretical step involves proving that under specific conditions, the optimal MMF solution corresponds to a state where the rates (or effective SNRs) of all users are balanced.

Key Contributions
The paper outlines three primary contributions:

Theoretical Derivation: The authors analytically derive the relationship between rate balancing and the optimal MMF multicasting solution.
Low-Complexity Algorithm: Based on the theoretical insight, they propose an algorithm that yields closed-form solutions, avoiding the need for iterative convex solvers like CVX.
Conditions for Optimality: The paper establishes specific conditions under which rate balancing is guaranteed to be the optimal solution. Specifically, Theorem 2 states that if the channel vectors of $K$ users are linearly independent and $K \le M$ (where $M$ is the number of transmit antennas), the balanced rate solution is optimal. Conversely, if $K > 2M$ , unbalanced rates are required for optimality. For the intermediate case ( $M < K \le 2M$ ), optimality depends on the rank of the derived matrix $A$ .

Results and Discussion
Numerical simulations were conducted using 3GPP channel specifications to validate the proposed algorithm (denoted as "Algo RB") against SDR-based methods (CVX Rand, CVX Relaxed), ADMM, and heuristic SNR increment methods.

Underloaded Scenario ( $M=10, K=5$ ): The proposed algorithm performs comparably to the high-complexity CVX solutions and slightly better than ADMM and SNR Inc. In this regime, the results confirm that all optimal solutions result in balanced user SNRs.
Overloaded Scenario ( $M=8, K=10$ ): Despite $K > M$ , the specific channel realization resulted in an invertible matrix $D$ , allowing the direct application of the proposed algorithm without searching for an active user subset. Here, the proposed algorithm outperformed all other methods, including the high-complexity CVX Rand.
Rate Balancing Validation: The simulations demonstrate that while heuristic methods (ADMM, SNR Inc.) achieve near-optimal minimum SNR, they often result in unbalanced user rates. In contrast, the proposed method and the relaxed CVX upper bound achieve balanced rates, confirming the theoretical link between rate balancing and optimality when the system matrix is invertible.

Significance and Claims
The authors claim that this work is the first to establish a direct connection between rate balancing and the optimal MMF multicasting solution. The significance lies in transforming an NP-hard problem into a low-complexity algorithm with closed-form solutions under practical conditions (specifically $K \le M$ with linearly independent channels). This is particularly relevant given the industry trend toward massive MIMO systems where the number of antennas often exceeds the number of users. The paper modestly notes that future work will address the efficient identification of the active user set for cases where $K > M$ and the matrix $D$ is not invertible, as well as handling collinear channels.