-------------------------------------------------------------------------- 9th DIMACS Implementation Challenge Workshop: Shortest Paths Call for papers http://www.dis.uniroma1.it/~challenge9 -------------------------------------------------------------------------- Goals Shortest path problems are ones of the most fundamental combinatorial optimization problems with many applications, both direct and as subroutines in other combinatorial optimization algorithms. Algorithms for these problems have been studied since 1950's and still remain an active area of research. One goal of this Challenge is to create a reproducible picture of the state of the art in the area of shortest path algorithms. To this end we are identifying a standard set of benchmark instances and generators, as well as a benchmark implementations of well-known shortest path algorithms. Another goal is to enable current researchers to compare their codes with each other, in hopes of identifying the more effective of the recent algorithmic innovations that have been proposed. The final goal is to publish proceedings containing results presented at the Challenge Workshop, and a book containing the best of the proceedings papers. -------------------- Scope The Challenge addresses a wide range of shortest path problems, including all sensible combinations of the following: * Point-to-point, single-source, all-pairs. * Non-negative arc lengths and arbitrary arc lengths (including negative cycle detection). * Directed and undirected graphs. * Static and dynamic problems. The latter include those dynamic in CS sense (arc additions, deletions, length changes) and those dynamic in OR sense (arc transit times depending on arrival times). * Exact and approximate shortest paths. * Compact routing tables and shortest path oracles. Implementations on any platform of interest, for example desktop machines, supercomputers, and handheld devices, are encouraged. -------------------- How to participate People interested in submitting papers to the Challenge Workshop can find benchmark instances, generators, and code for the problems they address at the Challenge website, along with detailed information on file formats. Your work can take two different directions. 1. Defining instances for algorithm evaluation. The instances should be natural and interesting. By the latter we mean instances that cause good algorithms to behave differently from the other instances. Interesting real-life application data are especially welcome. 2. Algorithm evaluation. Description of implementations of algorithms with experimental data that supports conclusions about practical performance. Common benchmark instances and codes should be used so that there is common ground for comparison. The most obvious way for such a paper to be interesting (and selected for the proceedings) is if the implementation improves state-of-the-art. However, there may be other ways to produce and interesting paper, for example by showing that an approach that looks well in theory does not work well in practice by explaining why this is the case. -------------------- Challenge Book The best papers presented at the Challenge Workshop will be selected for publication in a book published in the DIMACS Book Series. -------------------- Important dates - August 25, 2006: Paper submission deadline - September 25, 2006: Author notification - November 13-14, 2006: Challenge Workshop, DIMACS Center, Rutgers University, Piscataway, NJ -------------------- Organizing Committee Camil Demetrescu, University of Rome "La Sapienza" Andrew Goldberg, Microsoft Research David Johnson, AT&T Labs - Research -------------------- Advisory Committee Paolo Dell'Olmo, University of Rome "La Sapienza" Irina Dumitrescu, University of New South Wales Mikkel Thorup, AT&T Labs-Research Dorothea Wagner, Universität Karlsruhe -------------------------------------------------------------------------- -- ________________________________________________________oo_____ Camil Demetrescu, Ph.D. - http://www.dis.uniroma1.it/~demetres Dept. Computer and System Sciences, Univ. of Rome "La Sapienza" Via Salaria, 113 - 00198 Roma, Italy, ph. +39-06-4991-8457