9th DIMACS Implementation Challenge: Shortest Paths
- From: "Camil Demetrescu" <demetres@xxxxxxxxxxxxxxx>
- Date: 28 Jul 2005 04:16:34 -0700
-------------------------------------------------------------------------
9th DIMACS Implementation Challenge: Shortest Paths
Call for participation
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.
--------------------
Problems addressed:
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.
--------------------
Who can participate?
This challenge is open to anyone who wishes to participate.
Participants can submit either algorithms or problem instances.
Participants may submit results for as many algorithms as they wish.
If you are interested in participating in the Challenge, send email to
dsj@xxxxxxxxxxxxxxxx to let us know of your plans.
--------------------
How to participate
Participants 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. 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.
--------------------
Schedule
The Challenge will have three phases. The first phase will be devoted
to collecting and improving testbeds. During the second phase
algorithms and codes are evaluated and improved. The second stage
culminates in a workshop with talks describing testbeds and
implementations. In the post-workshop phase, papers describing the
most interesting results of the Challenge are assembled into a book
refereed Proceedings. As with previous Challenges, we expect that the
website with benchmarks will remain accessible after the Challenge is
complete. We plan to have initial collection of benchmark instances
and codes available by September 30, 2005, officially starting the
first phase. We expect the second phase to be completed by March 31,
2006, at which point benchmarks will be finalized and the second phase
starts. The deadline for submitting papers to the workshop is August
25, 2006. The workshop will take place in November 2006.
--------------------
Important dates
- September 30, 2005:
Start of Phase 1 devoted to collecting and improving testbeds.
- March 31, 2006:
Start of Phase 2 devoted to evaluating algorithms.
- August 25, 2006:
Deadline for submitting algorithm implementation papers.
- November 2006:
Workshop. Start of Phase 3 devoted to assembling the Challenge book.
--------------------
Organizing Committee
Camil Demetrescu, University of Rome "La Sapienza"
Andrew Goldberg, Microsoft Research
David Johnson, AT&T Labs - Research
Questions and comments should be sent to dsj@xxxxxxxxxxxxxxxxx
-------------------------------------------------------------------------
Message Sender:
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
.
- Prev by Date: Re: Physicists as programmers
- Next by Date: Re: OO compilers and efficiency
- Previous by thread: format for data storage?
- Next by thread: Protecting your code
- Index(es):
Relevant Pages
|
