Quote from: btc78 on Today at 03:22:02 AM

Knapsack problem is basically ensuring that you maximize the items with most value. Miners can maximize profits straightforwardly by choosing transactions with the highest fees subjected to size.

That would be the Greedy Approach, which rarely grant you a local maxima. The issue with knapsack lies predominantly with the size of each item that is supposed to be packed in a bag of a certain size. Hence, the problem of which to pack becomes a key decision to make. In operations research, we usually formulate it as a DP approach which would probably gain better results than Greedy.

Quote from: btc78 on Today at 03:22:02 AM

Using complex and sophisticated LP solvers will actually just slow down a miner which is not ideal.

Transaction selection can be done concurrently. The way that miners work now is that they will build an empty block upon receiving a new block, before consolidating the transactions together. An easy way to think of a profit maximization would be to attempt to increase the value by selecting another set of transactions on-top of the Greedy method. As fees becomes the main revenue for miners, I expect marginal gains to be the priority.