large-scale algorithms

Real-Time Approximate Routing for Smart Transit Systems

We study real-time routing policies in smart transit systems, where the platform has a combination of cars and high-capacity vehicles (e.g., buses or shuttles) and seeks to serve a set of incoming trip requests. The platform can use its fleet of cars …

Real-Time Approximate Routing for Smart Transit Systems

We study real-time routing policies in smart transit systems, where the platform has a combination of cars and high-capacity vehicles (e.g., buses or shuttles) and seeks to serve a set of incoming trip requests. The platform can use its fleet of cars …

Computing Constrained Shortest-Paths at Scale

Motivated by the needs of modern transportation service platforms, we study the problem of computing constrained shortest paths (CSP) at scale via preprocessing and network augmentation techniques. Our work makes two contributions in this regard: …

Sublinear estimation of a single element in sparse linear systems

We present a fast bidirectional algorithm for estimating a single element of the product of a matrix power and vector. This is an important primitive in many applications; in particular, we describe how it can be used to estimate a single element in …

Personalized pagerank estimation and search: A bidirectional approach

We present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source distribution to a target node, we present a new bidirectional estimator …

Bidirectional PageRank Estimation: From Average-Case to Worst-Case

We present a new algorithm for estimating the Personalized PageRank (PPR) between a source and target node on undirected graphs, with sublinear running-time guarantees over the worst-case choice of source and target nodes. Our work builds on a recent …