Quote from: theymos on January 11, 2019, 06:18:12 PM

I thought that I had a good idea for limiting each individual truster when handling the last two criteria: set it up as a circulation problem as below, and then find the maximum flow. The "user tX"s through whom flow passes would be the DT1s selected.

https://i.imgur.com/JFDH3Qg.png

(The orders of the users would be randomized on each run.)

There are efficient algorithms for maximizing the flow in problems similar to this, which is why thinking about it in this way occurred to me. However, it turns out that the "exactly 0 or exactly 10" requirement on the rightmost edges makes finding an exact solution too difficult.

I might try to write an algorithm for finding an approximate solution to this, but I probably won't get to it in the near future. Anyone else want to give it a try? You might also be able to structure it as a knapsack problem or something else, but I haven't gotten around to thinking about that yet.

Crap, I wish I had paid more attention in my CS classes. No recollection of max flow whatsoever. Google is extremely unhelpful. So what's the range for X and how does it depend on merit? Can it be negative? How big is N - that's only users who have custom trust lists, right? I feel like I'm missing something obvious here.