[cfp] 9th DIMACS Implementation Challenge Workshop: Shortest Paths

--------------------------------------------------------------------------
       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
-- 
________________________________________________________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

Received on Friday, 9 June 2006 13:51:19 UTC