|
|
 |
|
9th DIMACS Implementation Challenge - Shortest Paths
|
|
To make the Challenge more fun, we will have a competition of the point-to-point algorithms on a road graph. We hope that most of the P2P paper contributors will be able to participate, and others will become fans of the competition. (Due to a conflict of interest, the algorithm of Goldberg, Kaplan, Werneck will not be eligible for the competition, but we will run it and provide the results as a proof that the problem is feasible.)
The competition will work in the following way.
- We will use the USA road graph with a modified length function. The modification will be announced in the morning of the first day of the workshop.
- Competitors will use their own hardware, either by a remote connection or by giving instructions to their colleagues back home. (If your code runs on your laptop, it is OK too.)
- The results will be due at the end of the lunch break of the second day of the workshop.
- The winner will be judged based on the average time for 1,000 queries between random vertex pairs. If possible, both the time to compute the distance and time to compute the distance plus the time to "traverse" the path should be reported. For the latter, your code should visit all original arcs on the path and add up their lengths. We would also like to get additional information: the preprocessing time, the average and the maximum number of vertex scans.
- To calibrate runtimes, participants should report technical data for the machine on which queries were performed in the format described, and the results of running the benchmark solver on the graph. The latter can be done after the results of the queries are due, but we would like to have the benchmark times before the competition summary session.
- The competitors are encouraged to prepare the 1,000 query pairs, the benchmark code, and the USA graph in advance. The modification to the graph will be easy to make.
- We will not be checking correctness of the results, but we expect that the participants will have correctness checking in their codes. Correctness checking time should not count in the computation time, and the participants can make a separate correctness-checking run if needed.
- In addition to having fun, the goal of the competition is to check robustness of the different implementations. Thus the competitors must not tune or modify their code except possibly the parser or to the graph initialization to implement the length function modification.
Announcement (Nov 13, 2006):
The graph used in the competition is the full strongly connected USA graph with unit arc lengths [download .gr.gz file, 225 MB]
More instructions for people participating in the competition are now available at the URL: http://www.dis.uniroma1.it/~challenge9/temp.