# How to linearize your cluster

**URL:** <https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303>\
**Category:** Implementation\
**Tags:** wg-cluster-mempool, mempool\
**Created:** [December 18, 2023, 8:55pm UTC](https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303 "2023-12-18T20:55:14Z")\
**Posts on this page:** 1\
**Showing post:** 15

<div class="post-metadata">

**Author:** ![stefanwouldgo](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/stefanwouldgo/32/664_2.png) [@stefanwouldgo](https://delvingbitcoin.org/u/stefanwouldgo)\
**Post date:** [February 1, 2025, 7:33am UTC](https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303/15 "2025-02-01T07:33:33Z")

</div>

> [@sipa](#):
>
> I do wonder: what was your query, and what was the response that you learned this from?

Here’s my prompt:

> Here’s a mathematical problem: let G be a directed graph. We call a subset of its nodes topological if it includes all its ancestors. Now let’s assume every node of the graph has two integer properties called size and fee, and a derived property called feerate=fee/size. The feerate of a set of nodes is the sum of their fees divided by the sum of their sizes. Can you give an algorithm that finds the highest feerate topological subset of a given directed graph?

DeepSeek-R1 thought about this for about two minutes (and it always puts out its thought process, which is very interesting, but for some reason I cannot copy from the iOS App I did this in) and then it answered

> To solve the problem of finding the highest feerate topological subset in a directed graph, we can use a binary search approach combined with a max-flow/min-cut algorithm. Here’s the step-by-step algorithm:
> 
> ### Algorithm
> 
> 1. Binary Search Setup:
> 
> 2. Binary Search Loop:
> 
> 3. Flow Network Construction:
> 
> 4. Max-Flow/Min-Cut Computation:
> 
> 5. Decision:
> 
> 6. Extract Optimal Subset:
> 
> 7. Result:
> 
> ### Explanation
> 
> - Binary Search: Efficiently narrows down the possible feerate values, leveraging the monotonicity of the feerate function.
> - Flow Network Transformation: Converts the problem of finding a maximum weight closed set into a max-flow problem, ensuring the subset includes all ancestors.
> - Min-Cut Interpretation: The min cut in the flow network corresponds to the optimal subset, balancing the inclusion of high-feerate nodes and exclusion of low-feerate ones.
> 
> This approach ensures we efficiently find the subset with the highest feerate while respecting the topological constraints, using polynomial-time algorithms for max-flow.

I first didn’t believe it so I asked it for a proof that the problem is hard and it correctly answered me that it isn’t. Then I asked for a correctness proof, which didn’t really convince me, but from my understanding of the ideas in the algorithm and the thought process I started to believe that this could actually work.

So I asked to find a precise runtime bound, and the answer was a little meh (and included log U). I then suspected that it might be possible to lose that U and asked it

> Can we refine this analysis (make it independent of U) by only taking into account lambda steps that change the sign of a node’s weight?

The answer was really handwavy, but pointed in the right direction. But when I asked it

> Where has this technique of ratio maximization using a Lagrange multiplier been first introduced?

the answer was

> The technique of maximizing a ratio (e.g., fee/size) by introducing a parameter ( \lambda ) and converting it into a feasibility problem (e.g., checking if ( \text{fee}(S) - \lambda \cdot \text{size}(S) \geq 0 )) is rooted in Dinkelbach’s algorithm for fractional programming. This approach is analogous to using a Lagrange multiplier to handle the ratio objective, though it differs in its exact mechanics. Here’s a breakdown of its origins and key milestones:
> 
> * * *
> 
> ### 1. Foundational Work: Fractional Programming
> 
> - Wolfgang Dinkelbach (1967) introduced the parametric method for solving nonlinear fractional programs in his seminal work:
> - Title: _“On Nonlinear Fractional Programming”_ (Management Science, 1967).
> - Key Idea: Transform the problem of maximizing ( \frac{f(x)}{g(x)} ) into solving ( f(x) - \lambda g(x) = 0 ) via iterative updates of ( \lambda ).
> - This is the earliest formalization of the technique used in the algorithm.
> 
> * * *
> 
> ### 2. Application to Combinatorial Optimization
> 
> The adaptation of this parametric approach to combinatorial problems (e.g., graph subsets with constraints) emerged later, notably in:
> 
> - Jean-Claude Picard (1976):
> 
> - Gallo, Grigoriadis, and Tarjan (1989):
> 
> * * *
> 
> ### 3. Modern Adaptations for Ratio Maximization
> 
> The specific use of this technique for feerate-like ratio maximization (e.g., density maximization ( \frac{\text{sum of weights}}{\text{size}} )) was popularized in:
> 
> - Charikar (2000):
> 
> - Goldberg (1984):
> 
> * * *
> 
> ### Why It’s Linked to Lagrange Multipliers
> 
> The parameter ( \lambda ) acts similarly to a Lagrange multiplier in constrained optimization:
> 
> - It balances the trade-off between the numerator (fee) and denominator (size) in the ratio.
> - However, unlike classical Lagrange multipliers (which handle equality/inequality constraints), this method uses ( \lambda ) to transform the ratio objective into a sequence of feasibility checks.
> 
> * * *
> 
> ### Key Takeaway
> 
> The technique was first introduced by Dinkelbach (1967) for general fractional programming. Its adaptation to graph problems (e.g., maximum density subgraph, topological subsets) emerged in the 1980s–2000s through the integration of parametric max-flow algorithms. The modern flow-based implementation for ratio maximization in directed graphs is largely attributed to Gallo-Grigoriadis-Tarjan (1989) and later refinements by Goldberg and others.

And this finally convinced me to read GGT, where I found that they actually completely solve this problem as an application of their general technique. Which is something that the AI hasn’t really told me, it stuck to a bisection approach. But it has helped me find the key paper which would have been very hard otherwise.

---

_[View the full topic](https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303)._