DIMACS Fifth Implementation Challenge: Priority Queues, Dictionaries, and Point Sets: Program

  40 minute talks (plus two 30-minute survey talks) on Monday, Tuesday.
  25 minute talks on Wednesday. 

Monday, October 28th: Dictionaries

 8:30   Coffee and bagels. 

 9:10   Greetings from DIMACS 
	Steve Mahaney, Associate Director

 9:15   History of the DIMACS Challenge (DSJ)

 9:45   Remarks about the Fifth Challenge (CCM)

10:15   Tutorial on dictionary implementation techniques.  

10:45   BREAK 

11:15   Jyrki Katajainen and Michael Lykke
	University of Copenhagen (Denmark) 
	``Experiments with universal hashing.''

12:00   LUNCH at DIMACS 

 1:00   Martin Deitzfelbinger and Martin Huhne 
	Universitat Dortmund 
	``A dictionary implementation based on dynamic perfect hashing.'' 

 1:45   Craig Silverstein
	Stanford University 
	``A practical perfect hashing algorithm.'' 

 2:30   Arne Andersson
	Lund University (Sweden) 
	which flavor of balanced tree? 

 3:15   BREAK 

 3:45   Roberto Battiti
	University of Trento (Italy) 
	``Time and Space-efficient data structures for 
        history-based heuristics: a C++ implementation.

 4:30   Madhukar Korupolu, Ramgopal Mettu, Vijaya Ramachandran, Yuke Zhao
	University of Texas at Austin  
	``Experimental evaluation of incremental 
        algorithms for graph connectivity and biconnectivity.'' 

 5:15   BREAK

 5:30   RECEPTION for workshop participants at DIMACS.  

Tuesday, October 29th: Priority Queues

 8:30   Coffee and bagels. 
 
 9:10   Announcements and Remarks.  
 
 9:15   Tutorial on priority queue implementation techniques. 
 
 9:45   Yossi Matias, Bell Laboratories; 
	Suleyman Cenk Sahinalp, University of Maryland;
	Neal Young, Dartmouth College 
	``Implementation and performance evaluation of
        approximate priority queues.''

10:30   BREAK

11:00   Arne Andersson and Mikkel Thorup, Lund University (Sweden)
	``Implementing monotone priority queues.''

11:45   Andrew Goldberg, NEC Research Institute  and 
	Craig Silverstein, Stanford University
	``Practical evaluation of HOT queues.''

12:30  LUNCH  
 
 2:00  Panel Discussion on results of the Fifth DIMACS Challenge.  
 
 3:30  BREAK
 
 4:00  Panel Discussion on the future of the DIMACS Challenge. 
 
 5:00  DONE 

Wednesday, October 30th: Methods and standards

 8:30   Continental breakfast. 
 
 9:00   The Agenda. (Johnson, McGeoch) 
 
 9:10   David Johnson, AT&T Labs
	Do's and Don'ts in the Experimental Analysis of Algorithms
 
 9:30   Bernard Moret, University of New Mexico
	Toward a discipline of experimental algorithmics

 9:50   Richard Anderson, University of Washington

10:10   Irv Lustig, CPLEX
	Report from the War Zone: Reflections Past Experiments

10:40   BREAK

11:10   Jon Bentley, Bell Laboratories  

11:30   Roberto Battiti, University of Trento 
	Machine Learning Methods for Parameter Tuning in Heuristcs

11:50   Nate Dean, Bell Labs
        The Link project

12:10   LUNCH
 
 1:10   Cathy McGeoch, Amherst College
 
 1:40   Jim Orlin, MIT 

 1:50   Panos Pardalos, Univeristy of Florida
        Test Problem Generation and Test Problem Collections
 
 2:10   Andrew Goldberg, NEC Research Institute
	What to Solve: Problems for Algorithm Evaluation
 
 2:40   BREAK
 
 3:00   Panel discussion on standards and methods in experimental 
        analysis of algorithms.  

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage