How to linearize your cluster

Woah, :exploding_head:.

The GGT algorithm min-cut based algorithms are effectively finding a subset x which maximizes

\operatorname{fee}_x - \lambda \operatorname{size}_x

for a given existing solution S with feerate \lambda. In order words, it maximizes

\operatorname{fee}_x - \frac{\operatorname{fee}_S}{\operatorname{size}_S} \operatorname{size}_x

which, given that \operatorname{size}_S is a constant in this context, is the same as maximizing

\operatorname{fee}_x\operatorname{size}_S - \operatorname{fee}_S\operatorname{size}_x

Which is what I’ve called q(x, S) in the spanning-forest writeup, the quantity being maximized when performing chunk splits…

2 Likes