LIMO: combining the best parts of linearization search and merging

Implementation
6

Huh, much simpler construction that also seems to work:

  • Given an initial linearization L
    • While there are transactions left in L:
      • Compute high-feerate topologically-valid sets S_1 and S_2.
      • Let b be the highest-feerate set in:
        • \Pi(Q) for Q \in \{L, L[S_1], L[S_2], L[S_1 \cap S_2]\}
      • Append L[b] to output linearization.
      • Remove b from L and repeat.

(also generalizes to triple variant)

1 Like