Computational Challenges: What happens
when the Problem Size becomes Large?
Abstract
In introductory courses, students learn that certain
problems admit elementary solutions while others
seem to be intractable - even for modest size input.
But even an elementary problem can become quite challenging
when the problem size becomes large. In this talk, we
consider implementations of shortest path algorithms and
the effect of implementation details (especially the
data structures used in the implementation)
on running time.
We consider graphs with more than 100,000 nodes and
a family of codes first implemented by Cherkassky,
Goldberg, and Radzik. The codes have been tested on
many of the machines available here in the department
including math, euclid, jacobi, and ultra as well as
on several PC's. The results are a little surprising.
