09254987 
 553c2b60 
 XPost: cs.bboard, columbia.general.bboard 
 From: rocco@news.cs.columbia.edu 
  
 Andrew Goldberg will give a joint IEOR/CS seminar tomorrow at 1:30 in 
 Uris 307 (note unusual time and location).  Title/abstract are below. 
  
 Hope to see you at Uris tomorrow, 
  
 Rocco 
  
 __________________________________ 
  
 TALK:   A* Search with Triangle Inequality 
         Tuesday, March 22nd, 2005 
         2:30 pm -- 3:45 pm 
         Interschool Lab, 7th Floor CEPSR 
  
 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)