Implementation Challenge for TSP Heuristics
- PDF / 2,559,732 Bytes
- 22 Pages / 547.087 x 737.008 pts Page_size
- 36 Downloads / 235 Views
I
I
Implementation Challenge for Shortest Paths 2006; Demetrescu, Goldberg, Johnson CAMIL DEMETRESCU1 , ANDREW V. GOLDBERG2 , DAVID S. JOHNSON3 1 Department of Information and Computer Systems, University of Roma, Rome, Italy 2 Microsoft Research – Silicon Valley, Mountain View, CA, USA 3 Algorithms and Optimization Research Dept., AT&T Labs, Florham Park, NJ, USA Keywords and Synonyms Test sets and experimental evaluation of computer programs for solving shortest path problems; DIMACS
of algorithms. And it is a step in technology transfer by providing leading edge implementations of algorithms for others to adapt. The first Challenge was held in 1990–1991 and was devoted to Network flows and Matching. Other addressed problems included: Maximum Clique, Graph Coloring, and Satisfiability (1992–1993), Parallel Algorithms for Combinatorial Problems (1993–1994), Fragment Assembly and Genome Rearrangements (1994–1995), Priority Queues, Dictionaries, and Multi-Dimensional Point Sets (1995–1996), Near Neighbor Searches (1998–1999), Semidefinite and Related Optimization Problems (1999– 2000), and The Traveling Salesman Problem (2000–2001). This entry addresses the goals and the results of the 9th DIMACS Implementation Challenge, held in 2005–2006 and focused on Shortest Path problems. The 9th DIMACS Implementation Challenge: The Shortest Path Problem
Problem Definition DIMACS Implementation Challenges (http://dimacs. rutgers.edu/Challenges/) are scientific events devoted to assessing the practical performance of algorithms in experimental settings, fostering effective technology transfer and establishing common benchmarks for fundamental computing problems. They are organized by DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science. One of the main goals of DIMACS Implementation Challenges is to address questions of determining realistic algorithm performance where worst case analysis is overly pessimistic and probabilistic models are too unrealistic: experimentation can provide guides to realistic algorithm performance where analysis fails. Experimentation also brings algorithmic questions closer to the original problems that motivated theoretical work. It also tests many assumptions about implementation methods and data structures. It provides an opportunity to develop and test problem instances, instance generators, and other methods of testing and comparing performance
Shortest path problems are among 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 the 1950’s and still remain an active area of research. One goal of this Challenge was to create a reproducible picture of the state of the art in the area of shortest path algorithms, identifying a standard set of benchmark instances and generators, as well as benchmark implementations of well-known shortest path algorithms. Another goal was to enable current researchers to compare their c
Data Loading...
