Comment:
Time taken for the gossip to come back?
Follow-up:
A circular gossiping loop is a round trip tour visiting each and every node once. The cost of such a tour is defined as the total costs summing up all the link costs. Each link cost can represent the time needed for the gossip message to travel from one node to another node.
Comment:
Why is there no fast algorithm for a round trip tour where each link and node is visited once?
Follow-up:
That is life, I guess. There are in fact many such seemingly simple problems that do not have a fast optimal algorithm for them yet.
Showing posts with label travel scheduling. Show all posts
Showing posts with label travel scheduling. Show all posts
Thursday, July 21, 2011
Principles of the travel scheduling problem
Comment:
Underlying principles of the travel scheduling problem?
Follow-up:
Frankly speaking we also do not know the complete picture of this problem. Yet from an intuitive angle, the problem enlarges the complexity of the original shortest path problem in at least two dimensions. Firstly, we need to solve multiple instances of the shortest path problem for any single round-trip tour (e.g., one day in the trip). Secondly, we need to combine these shortest path solutions temporally across different tours so as to obtain the minimum overall cost for the whole trip.
Underlying principles of the travel scheduling problem?
Follow-up:
Frankly speaking we also do not know the complete picture of this problem. Yet from an intuitive angle, the problem enlarges the complexity of the original shortest path problem in at least two dimensions. Firstly, we need to solve multiple instances of the shortest path problem for any single round-trip tour (e.g., one day in the trip). Secondly, we need to combine these shortest path solutions temporally across different tours so as to obtain the minimum overall cost for the whole trip.
Sunday, July 17, 2011
Dijkstra's shortest path, Computation
Comment 1:
How to derive the Dijkstra’s shortest path algorithm’s estimated running time?
Follow-up:
As an approximation, we note that each link needs to be visited at once. In the worst case, we can have on the order of (n x n) links, where n is the number of nodes in the graph. Thus, the estimated running time is approximately (n x n) steps.
Comment 3:
Maybe it is true that if we put in more computing/storage resources, we can solve just about any problem.
Follow-up:
If you attended Tutorial 3, you should have learned that there are really difficult problems, in the sense that you will need unreasonably large amount of storage (e.g., every atom in the universe) and computing power to solve. Furthermore, in Problem 3 of Tutorial 3, you will see that there are problems that are simply unsolvable.
How to derive the Dijkstra’s shortest path algorithm’s estimated running time?
Follow-up:
As an approximation, we note that each link needs to be visited at once. In the worst case, we can have on the order of (n x n) links, where n is the number of nodes in the graph. Thus, the estimated running time is approximately (n x n) steps.
Comment 3:
Maybe it is true that if we put in more computing/storage resources, we can solve just about any problem.
Follow-up:
If you attended Tutorial 3, you should have learned that there are really difficult problems, in the sense that you will need unreasonably large amount of storage (e.g., every atom in the universe) and computing power to solve. Furthermore, in Problem 3 of Tutorial 3, you will see that there are problems that are simply unsolvable.
Subscribe to:
Posts (Atom)