C.V.: HTML, PostScript, PDF.
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:
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.
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 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):
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.
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 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:
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.
Devotionals Celebrating Sunnyvale First United Methodist Church's Centennial:
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:
Avoiding Fraud: Tips for Individuals: PDF, slides.
Selling Spontaneous Charitable Services: PDF, HTML.
oldham at cs dot stanford dot edu (email)
http://theory.stanford.edu/~oldham (WWW): PostScript, PDF.
My Ph.D. Advisor: Serge Plotkin
Stanford Theory Group
Stanford Computer Science Department
LATEX2HTML Manual: HTML, PostScript.
MCMCF Manual: HTML, PostScript, PDF