Instant approximate 1-center on road networks via embeddings
Samidh Chatterjee, Bradley Neff, Piyush Kumar · 2011
We study the 1-center problem on road networks, an important problem in GIS. Using Euclidean embeddings, and reduction to fast nearest neighbor search, we devise an approximation algorithm for this problem. Our initial experiments on real world data sets indicate fast computation of constant factor approximate solutions for query sets much larger than previously computable using exact techniques.