An optimal algorithm for the Bottleneck
transportation problem with a fixed number of sources
Abstract
We investigate a special case of the Bottleneck transportation problem
where the number s of sources is bounded by a constant and not part
of the input.
For the subcase s=2, a best possible linear time algorithm has been
derived by Varadarajan [Operations Research Letters 10 (1991), 525--529].
In this note we show that for any fixed number s >= 1, the Bottleneck
transportation problem with s sources can be solved in linear time.
The algorithm is conceptually simple and easy to implement.
Download Information
Click on the following title to view and download the paper in PostScript format.
- An optimal algorithm for the
Bottleneck transportation problem with a fixed number of sources (6 pages, 369 KB)
,
- Dorit S. Hochbaum and Gerhard J. Woeginger. Operations
Research Letters. 24, 1999, 25-28.
dorit@hochbaum.ieor.berkeley.edu
7/30/98