Hacker News new | ask | show | jobs
by Thiez 3471 days ago
Perhaps a different analogy would be better, e.g. ordering materials when building a house. If you can only order one material at a time, you would probably want to order the concrete for laying the foundation before ordering the roof tiles. Loading website resources is a lot like that (at least compared to the travelling salesman).
1 comments
saurik 3471 days ago
This still smells NP Hard. I mean, in practice for simple dependencies it is probably quite tractable, but this is a combinatorial optimization problem that seems pretty similar to an online modification to Job Shop Scheduling, where the material requirements map loosely to machine-task pairings that would be unblocked by orders, acting to make the problem more complex, not easier.
link
Thiez 3470 days ago
Your sense of smell is off. Assuming a directed acyclic graph (the usual shape of a dependency tree), assume we write the result order to a list L. Walk over all vertices once, create a mapping M of each vertex to its number of incoming edges, and add all vertices without incoming edges to a list R. This is O(|V| + |E|). Now, pick the first item of R and append it to L. For each outgoing edge in the item we chose, decrement the associated count of its receiving vertex in M by 1. For each item where the count becomes 0, append it to R. Keep running until R is empty, and you're done. This second part of the process is again O(|V| + |E|).

We're done and found a topological order in O(|V| + |E|).

link
saurik 3470 days ago
Yes, I know that topological sort is O(|V| + |E|). What I am claiming is that the problem of buying building materials in an optimal order isn't topological sort: there are numerous topological orders of a graph, but some will be much much slower than others to build at your construction site. To determine which of the many possible orders is the fastest one, you have to take into account how long various tasks will take and how many workers you have available for those tasks. When you get some materials, that unlocks certain parts of the gantt chart of what sounds like Job Shop Scheduling. To me, this is the same form of complaint as pointing out that Traveling Salesman isn't Topological Sort.
link
ooqr 3471 days ago
"If someone gave you the entire list of cities ahead of time, you could plan the fastest possible route."

Dynamic programming. So it saves time in the end.

link