Jeffrey D. Oldham

Résumé Network Flows Other Academic Addresses Links

I am a Ph.D. graduate from the theory group of the Stanford Computer Science Department. I develop and implement fast algorithms.


Résumé: HTML, PostScript, PDF, text.
C.V.: HTML, PostScript, PDF.

Networks Flows

The multicommodity minimum-cost flow problem involves simultaneously shipping multiple commodities through a single network so the total flow obeys arc capacity constraints and has minimum cost. For example, in telephone networks, calls between different locations must be routed through the same telephone cables which have finite capacities and differing costs.

My program MCMCF solves the multicommodity minimum-cost flow problem using gradient optimization and theoretically efficient algorithms. In practice, the implementation is two to three orders of magnitude faster than linear-programming based implementations.

Integer Programming and Combinatorial Optimization 1998: PostScript, compressed PostScript, PDF, compressed PDF.
Technical Report STAN-CS-TR-97-1600: PostScript, compressed PostScript, PDF, compressed PDF.
IPCO 98 Presentation: portrait PostScript, compressed portrait PostScript, portrait PDF, compressed portrait PDF, landscape PS, landscape PDF.
Another Presentation: PostScript, PDF (hard to read but prints well).
Shorter Presentation: PostScript (portrait or landscape orientation), PDF (portrait orientation), Audio.

Multicommodity No-Cost Flows

The multicommodity no-cost flow problem omits arc costs. The feasibility variant is to determine whether all the demands can be satisfied given the arc capacity constraints. The optimization variant is to determine what fraction of the arc capacities is needed so the commodities' demands can be satisfied.

Technical Report: (in preparation).

Generalized Flow Problems

Generalized network flow problems generalize ordinary network flows by linearly scaling flows as they travel through arcs. Using these flow multipliers permits modelling lossy transit and also conversions between various types, e.g., currency transactions. We present a new algorithm for the generalized shortest paths problem which can be used to yield combinatorial approximation algorithms for all generalized network flow problems. We also present a logarithmic-time PRAM algorithm for the all-sources generalized shortest paths problem.

Shortest Paths (draft): PostScript, compressed PostScript, PDF, compressed PDF.
Shortest Paths (shorter SODA version): PostScript, compressed PostScript, PDF, compressed PDF.
Presentation at Bonn Workshop: PostScript, compressed PostScript, PDF, compressed PDF.
All-Sources GSPs (draft): PostScript, compressed PostScript, PDF, compressed PDF.

Other Academic Work

Persistent HTTP connections, included in the draft HTTP/1.1 protocol, permit several HTTP request/response messages to be sent using the same TCP connection. We experimentally evaluate policies to predict when to terminate persistent HTTP connections.

WWW8 Paper: PostScript, compressed PostScript, PDF, compressed PDF, HTML.
WWW8 Presentation: PostScript, compressed PostScript, PDF, compressed PDF.

The ParaScope Editor is an interactive tool to help users find and add parallelism to sequential ForTran programs. A technical report: PostScript, compressed PostScript.

I programmed almost all of the illustrations in Donald E. Knuth's The Art of Computer Programming, third edition, using the computer language MetaPost. Autographed copies are available upon request!

The Bay Area Transit Triathlon (BATT) is an empirical test of the San Francisco Bay Area public transportation system. You can hold the world's record for traveling among all three major airports using only public transportation. See the BATT rules and a report from the current world's record holder.

Non-Academic Writings


Devotionals Celebrating Sunnyvale First United Methodist Church's Centennial: HTML.
A Sermon Based on John 6: HTML, PostScript, PDF.
A Lesson About Translating 1 John 3:16: HTML, PostScript, PDF.
Part of a Lesson About Translating Exodus 3:16: HTML, PostScript, PDF.
A Devotional About Ehyeh Asher Ehyeh: HTML, PostScript, PDF.
Thirty Translations of Psalm 23: PDF.
God's Calling Humans: HTML, PostScript, PDF.
A Devotional About Carol: HTML, PostScript, PDF.
A Devotional About Financial Turmoil and Faith: HTML, PostScript, PDF.


Mutual Funds and Distributions: HTML, PostScript, PDF.
Avoiding Fraud: Tips for Individuals: PDF, slides.
Selling Spontaneous Charitable Services: PDF, HTML.

How to Contact Me

oldham at cs dot stanford dot edu (email) (WWW): PostScript, PDF.

Useful Links

My Ph.D. Advisor: Serge Plotkin
Stanford Theory Group
Stanford Computer Science Department
Stanford University
LATEX2HTML Manual: HTML, PostScript.
MCMCF Manual: HTML, PostScript, PDF
Electronic Journals

Résumé Multicommodity Flows Other Academic Addresses Links

oldham 2006-03-05