In my first year at CAM I worked together with David Williamson. We developed a simple and fast polynomial time primal algorithm for the generalized maximum flow problem.
In my third year I have worked with Richard Durrett on a one-dimensional stochastic spatial model for population genetics.
Starting in 2006 (second half of my third year) I started working with Huseying Topaloglu and Shane Henderson fromt the ORIE department, in what will hopefully be the topic of my dissertation, the application of approximate dynamic programming techniques to the problem of real time ambulance relocation (redeployment).
To be presented at INFORMS '06
Submitted to Annals of Applied Probability
Presented at SODA 06. Extended version submitted to Mathematical Programming
We consider a stylized version of the ambulance relocation problem. The goal is to minimize a function of the response times of all calls arriving within a finite horizon. Assuming a given dispatching strategy, we focus on obtaining good policies for the relocation of idle ambulances that allow the system to anticipate future calls. After presenting a dynamic programming formulation for this problem, we report on the implementation and experimental performance of approximate dynamic programming algorithms applied to it.
Consider a one dimensional stepping stone model with colonies of size N and per generation migration rate ν, or a voter model on Z with dispersal of order K. Sample one lineage at the origin and one at L. We show that if Nν/L and L/K2 converge to positive finite limits, then the genealogy of the sample converges to a pair of Brownian motions that coalesce after the local time of their difference exceeds an independent exponentially distributed random variable. The computation of the distribution of the coalescence time leads to a one dimensional parabolic differential equation with an interesting boundary condition at 0.
We give a simple primal algorithm for the generalized maximum flow problem that repeatedly finds and cancels generalized augmenting paths (GAPs). We use ideas of Wallacher [29] to find GAPs that have a good trade-off between the gain of the GAP and the residual capacity of its arcs; our algorithm may be viewed as a special case of Wayne’ s algorithm for the generalized minimum-cost circulation problem [30]. Most previous algorithms for the generalized maximum flow problem are dual-based; the few previous primal algorithms (including Wayne [30]) require subroutines to test the feasibility of linear programs with two variables per inequality (TVPIs). We give an O(mn) time algorithm for finding negative-cost GAPs which can be used in place of the TVPI tester. This yields an algorithm with O(m.log(mB)) iterations of O(mn) time to compute an epsilon-optimal flow, or O(m2 log(mB)) iterations to compute an optimal flow, for an overall running time of O(m3n log (mB)). The fastest known running time for this problem O(m2n log B), and is due to Radzik [24], building on earlier work of Goldfarb, Jin, and Orlin [15].