41 citations · 86 across the 15 of their papers we have counts for
5 papers · 1 filter
Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions
David J. Aldous, Charles Bordenave, Marc Lelarge
A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over sets A in {1,2,...,n}, the objective function |A| - \sum_i ξ_i 1(i \in A,i+1 \i…
Edge Flows in the Complete Random-Lengths Network
David J. Aldous, Shankar Bhamidi
Consider the complete n-vertex graph whose edge-lengths are independent exponentially distributed random variables. Simultaneously for each pair of vertices, put a constant flow be…
Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models
David Aldous
Consider networks on vertices at average density 1 per unit area. We seek a network that minimizes total length subject to some constraint on journey times, averaged over sourc…
Stochastic Models for Phylogenetic Trees on Higher-order Taxa
David Aldous, Maxim Krikun, Lea Popovic
Simple stochastic models for phylogenetic trees on species have been well studied. But much paleontology data concerns time series or trees on higher-order taxa, and any broad pict…
Short-length routes in low-cost networks via Poisson line patterns
David J. Aldous, Wilfrid S. Kendall
In designing a network to link n cities in a square of area n, one might be guided by the following two desiderata. First, the total network length should not be much greater than…