How to order/sort a 2D table of dependencies

Question

I'm curious if there is some higher level theory/approaches/algorithm to solving this problem I have.

I'm working on a network routing problem (a proprietary radio network). By way of example, I have a network of 5 devices. For each device, I can measure how well it can hear other devices. The 0th root node is interesting only as a source. So in table form, I might end up with something like:

    _0_ _1_ _2_ _3_ _4_
1 | 21   -  42  55   0
2 |  0  63   -  18  20
3 | 20   0   0   -   0
4 |  0   0  13   0   -

Each row indicates how well that device can hear the other 5 sources. What I want to do is sort them so that each device gets the best sum signals from preceding elements. So for this simple case, the ordering might be 1, 3, 2, 4. But it could just as well be 3, 1, 2, 4. In fact, this second would be better because 1 can hear both 0 and 3. 3, 2, 1, 4 would work as well.

I'm trying to determine what kind of algorithm I can use to order these. There's a bit of traveling salesmen to it, and I don't need a "best" sort. Just a probably pretty good sort. I need to scale up to 9 devices with 10 sources.

Any thoughts, help, nudges, tips, hints appreciated.

Answer 1

This problem can be modeled as a minimum feedback arc set problem, which is a NP-hard problem. The original graph is a complete directed graph, with the weight of each edge (v0, v1) being the signal strength from v0 to v1. After computing maximum feedback arc set, do a topological sort will give an ordering that has the maximum total signal.