Lisa Fawcett

Lisa Fawcett

Auto-generated profile, based on publicly available information

Lisa Fawcett

Google Research, USA

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
20 November 2023 in ACM Transactions on Spatial Algorithms and Systems
Verified
Journal Article
Open access
ASAli Kemal Sinop
Ali Kemal Sinop
LFLisa Fawcett
Lisa Fawcett
SGSreenivas Gollapudi
Sreenivas Gollapudi
Kostas KolliasKostas Kollias
Kostas Kollias
Generating alternative routes in road networks is an application of significant interest for online navigation systems. A high quality set of diverse alternate routes offers two functionalities - (a) support multiple (unknown) preferences that the user may have; and (b) robust changes in network conditions. We formulate a new quantification of the latter in this paper, and propose a novel method to produce alternative routes based on concepts from electrical flows and their decompositions. Our method is fundamentally different from the main techniques that produce alternative routes in road networks, which are the penalty and the plateau methods, with the former providing high quality results but being too slow for practical use and the latter being fast but suffering in terms of quality. We evaluate our method against the penalty and plateau methods, showing that it is as fast as the plateau method while also recovering much of the headroom towards the quality of the penalty method. The metrics we use to evaluate performance include the stretch (the average cost of the routes), the diversity , and the robustness (the connectivity between the origin and destination) of the induced set of routes.