I suspect the only problem more difficult than coin selection in a wallet is transaction ordering in a mempool. Miners (presumably) might like to maximize their fee revenue, but unconfirmed transactions often have complex relationships with other transactions -- including other unconfirmed transactions.

You may recall @spiral's blog post from earlier this year documenting the huge amount of work that has gone into mempool optimizations #1467434.

This paper formulates the mempool linearization problem: given a set of transactions with associated fees, sizes, and dependency relationships, compute a dependency-respecting transaction ordering that maximizes fee-rate efficiency while supporting efficient updates as the mempool evolves dynamically. The problem is characterized through a partition of transactions into disjoint dependency-respecting subsets ordered by decreasing aggregate fee rate, together with an equivalent LP formulation. Motivated by structural properties of basic feasible solutions in the simplex method, a new algorithm called spanning forest linearization (SFL) is developed.

I'm no math genius but this looks like Bitcoiners figuring out novel algorithms!

Operating directly on the transaction dependency graph, SFL iteratively merges and splits chunks of transactions to refine a global ordering, and is guaranteed to terminate at an optimal solution. Evaluation on both synthetic and real-world Bitcoin mempool data shows that SFL consistently computes optimal linearizations with substantially lower runtime than competing approaches, including a method based on the parametric preflow algorithm of Gallo, Grigoriadis, and Tarjan.

As with so many things in Bitcoin, I wonder if Satoshi realized how complicated the pieces of this system he set up were.