Aside: I have an optimization algorithm and I'm curious if ELO ranking (or TrueSkill) would be a decent approximate solution. I have a sparse matrix of probab

Aside: I have an optimization algorithm and I'm curious if ELO ranking (or TrueSkill) would be a decent approximate solution. I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over these edges. Most importantly, I want a solution that maintains the DAG property, i.e. no cycles. Given that constraint, I want to maximize the total probability of edges kept in the DAG combined with the (1 - probability) edges removed from the graph. Any suggestions on how to implement this optimization algorithm? Perhaps I could use an ELO or TrueSkill ranking as an approximation. The difficulty is sampling matches, but perhaps it makes sense to sample non-zero edges randomly, uniformly. So nodes with high in-degree or high out-degree are selected more frequently, since they are more likely to impose constraints on the graph. The probability of winning is determined by the edge probability. This doesn't guarantee a DAG but would be a great initialization point. Anyway, I'm curious about alternate ideas or refinements to the above.