e9f15ddb 
 09254987 
 XPost: cs.bboard, columbia.general.bboard 
 From: rocco@news.cs.columbia.edu 
  
 Hi all, 
  
 Apologies for the multiple inconsistencies in the previous email about 
 Andrew Goldberg's talk. 
  
 The correct information is that it will be on Thursday at 1:30pm in Uris 
 307. 
  
 Best, 
  
 Rocco 
  
 __________________________________ 
  
 TALK:   A* Search with Triangle Inequality 
         Thursday, March 24nd, 2005 
         1:30 pm -- 2:30 pm 
         Uris 307 
  
 SPEAKER: 
   Andrew Goldberg 
   Microsoft Research 
  
 ABSTRACT: 
  
 We study the problem of finding a shortest path between two given vertices 
 in a directed graph. This is an important problem with many applications, 
 including that of computing driving directions. We are interested in 
 preprocessing the graph using a linear amount of extra space to store 
 additional information, and using this information to answer shortest 
 paths queries quickly. 
  
 We use A* search in combination with new distance lower-bounding 
 techniques based on landmarks and triangle inequality. Our experiments 
 show that on some graph classes, such as map graphs, the new algorithm 
 works very well. In particular, we are able to solve the problem on the 
 graph of North America road networks with 30 million vertices on a 
 handheld device. In this talk we describe the algorithm, its 
 implementation, and experimental performance. 
  
 Joint work with Chris Harrelson and Renato Werneck 
  
 --- SoupGate-Win32 v1.05 
  * Origin: you cannot sedate... all the things you hate (1:229/2)