How to linearize your cluster

The publication available at https://www.wellesu.com/10.1137/0218003 delves into the intricacies of the "maximum-ratio closure problem," alternatively known as "maximum-feerate topologically-valid subset finding." This issue is primarily considered within a transaction graph context, characterized by dependencies, fees (both positive and negative), and sizes. The objective is to identify a topologically-valid subset of transactions that maximizes the fee, which is straightforward if all fees are positive since the entire graph would naturally constitute the maximal set. However, the presence of negative fees introduces complexities necessitating sophisticated algorithmic approaches.

Three primary methodologies emerge from the literature to tackle this problem, each with its unique approach and computational complexity. The first, stemming from E. L. Lawler's 1978 paper, employs a bisection search technique to ascertain the highest feerate ($\lambda$) for which a non-empty set exists, boasting a complexity of $\mathcal{O}(knm \log(n^2/m))$. Here, $n$ denotes nodes, $m$ edges, and $k$ the bit length of transaction sizes and fees.

The second method, introduced by J.C. Picard and M. Queyranne in 1982, involves maintaining a singular optimal solution while iteratively adjusting $\lambda$ to refine this solution, achieving an operational complexity of $\mathcal{O}(n^2 m \log(n^2/m))$. Notably, this approach suggests no more than $\mathcal{O}(n)$ iterations are necessary for convergence.

Lastly, an innovative approach by Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan in 1989 proposes a parametric min-cut strategy, rendering the graph itself parameterized by $\lambda$. This allows for a more generic solution process aimed at discovering the maximum $\lambda$, encapsulating a complexity of $\mathcal{O}(nm \log(n^2/m))$. Depending on the relationship between the number of dependencies and transactions, this could scale to $\mathcal{O}(n^2 \log{n})$ or $\mathcal{O}(n^3)$ for a single subset discovery, with potential escalations to $\mathcal{O}(n^3 \log{n})$ or $\mathcal{O}(n^4)$ for full linearization across multiple subsets.

While these approaches offer structured solutions to the maximum-ratio closure problem, advancements in minimum-cut algorithms since 1989 may present opportunities for further efficiency gains. The exploration of these methods highlights the ongoing evolution of algorithmic strategies in addressing complex optimization problems within networked systems.