Cool article, it's fun to see how many situations can be mapped to graph theory. The description of the cost function seems strange, since it's described in te

Cool article, it's fun to see how many situations can be mapped to graph theory. The description of the cost function seems strange, since it's described in terms of the distance from "the correct order". It's clear that there is no single correct order. If two movies disagree on the ordering, it is not necessarily the case that one of them is doing it "wrong". Mathematically, it seems like it would be better to see any given movie's ordering as a sample from a statistical distribution. That suggests that computing cost in confidence terms, as in the probability of generating that ordering given your assumed distribution, might make more semantic sense. So for example you could maybe use the frequency graphs from the article and sum up the surprise of each path from the first to last entry in your list. (Where "surprise" here is the inverse of how frequently one node follows another.) That's linear. Or you could do it quadratically by making a matrix of A-follows-B frequencies and then summing up all pairs of entries in your list (normalizing by the length of the list). The latter takes more of the graph structure into account. Which is also the other thing that seemed a bit odd -- it seems like the "A follows B" relationship is getting a little mixed up with "A immediately follows B". As in, clumping the generator-related roles together isn't the same thing as saying an intern should follow a principal, and the cost function shouldn't treat those constraints the same way. I don't know how much noise it introduces, but intuitively it seems like the algorithm probably ought to do an ordering and then a clumping. Or perhaps the opposite: do ordering within clumps ("everything with 'generator' in the name"), then treat the clump as a single component for the main ordering pass. The last thing is that the article seems to take NP-hardness too seriously. Sure, if you really had to consider every possible permutation, it would take too long. But there's way more than enough structure in the problem to take advantage of. Some very very conservative heuristics would surely dramatically reduce the size of the relevant N that participates in the core NP-hard problem. Your Traveling Salesman may have to visit 50 cities in each of Oregon and New York, but you know there's no point in making him fly back and forth between the states more than the minimally required (2). Write your algorithms in such a way that you don't need to even allow the possibility of putting the Gaffer behind the Intern Electrician's Boyfriend's Dog.